stack version. through a little complex.


  • 0
    Y
        public String serialize(TreeNode root) {
            if (root == null) return null;
            
            StringBuilder res = new StringBuilder();
            String left = serialize(root.left);
            String right = serialize(root.right);
            if (null == left && null == right) {
                return String.valueOf(root.val);
            }
            
            res.append(root.val + "[");
            
            if(null != left) res.append(left);
            res.append(',');
            if(null != right) res.append(right);
            
            res.append("]");
            return res.toString();
        }
    
        // Decodes your encoded data to tree.
        // 2[1,3]
        
        private void addChiild(TreeNode parent, TreeNode child, boolean isLeftChild) {
            if (isLeftChild) parent.left  = child;
            else             parent.right = child;        
        }
        
        public TreeNode deserialize(String data) {
            if (null == data) return null;
            
            // singe node tree
            if (-1 == data.indexOf('['))  return new TreeNode(Integer.valueOf(data));
            
            int n = data.length();
            Stack<TreeNode> stk = new Stack<>();
            TreeNode root = null;
            int num = 0;
            boolean nextLchild = true;
            for (int i = 0; i < n; ++i) {
                char c = data.charAt(i);
                switch (c) {
                    case '[': {
                        // create the previous node which should be a root.
                        TreeNode node = new TreeNode(num);
                        if (root == null) root = node;
                        else addChiild(stk.peek(), node, nextLchild);
                        
                        stk.push(node);
                        num = 0;
                        nextLchild = true;
                        break;
                    }
                    case ']':{
                        // is there a right subtree.
                        if (data.charAt(i - 1) != ',' && data.charAt(i - 1) != ']') {
                            addChiild(stk.peek(), new TreeNode(num), nextLchild);    
                        }
    
                        // the subtree of the root is done.
                        if (!stk.isEmpty()) stk.pop();
                        num = 0;
                        break;
                    }
                    case ',':{
                        // is there a left subtree.
                        if (data.charAt(i - 1) != '[' && data.charAt(i - 1) != ']') {
                            addChiild(stk.peek(), new TreeNode(num), nextLchild);                       
                        }
    
                        nextLchild = false;
                        num = 0;
                        break;
                    }
                    default: {
                        num = num*10 + (c - '0');                
                        break;
                    }
                }
            }
            
            return root;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.