Recursive Solution : Beats 99.7% Submissions


  • 0
    M

    We denote the tree as below
    We denote each empty child as "::"
    1
    / \
    2 3

    1:2:::3:::

    public class Codec {
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if(root == null){return null;}
            StringBuffer sb = new StringBuffer();
            preOrder(root, sb);
            
            //System.out.println(sb.toString());
            
            return sb.toString();
        }
        
        private void preOrder(TreeNode node, StringBuffer sb){
            if(node == null){
                sb.append(":");
                return;
            }
            sb.append(node.val);
            sb.append(":");
            preOrder(node.left, sb);
            preOrder(node.right, sb);
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if(data == null || data.isEmpty()){return null;}
            
            return buildTree(new IntWrapper(0),data.toCharArray());
        }
        
        private TreeNode buildTree(IntWrapper index, char c_tree[]){
            if(index.index >= c_tree.length || c_tree[index.index] == ':'){
                return null;
            }
            
            StringBuilder sb_num = new StringBuilder();
            
            while(index.index < c_tree.length && c_tree[index.index] != ':'){
                sb_num.append(c_tree[index.index]);
                index.index++;
            }
            
            TreeNode node = new TreeNode(Integer.valueOf(sb_num.toString()));
            
            index.index++;
            
            node.left = buildTree(index, c_tree);
            
            index.index++;
            
            node.right = buildTree(index, c_tree);
            
            return node;
        }
        
        private static class IntWrapper{
            int index;
            public IntWrapper(int index){
                this.index = index;
            }
        }
    }
    

Log in to reply
 

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