Easy Java preOrder solution O(n), beats 99.3%


  • 0
    C

    When serializing a tree [2, 1, 3], the string will be "[2[1[][]][3[][]]]". Tree deserialization only needs to scan the string once.

    public class Codec {
    
        int pos;
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            ser(sb,root);
            return sb.toString();
        }
    
        private void ser(StringBuilder sb, TreeNode n){
            sb.append('[');
            if(n!=null){
                sb.append(n.val);
                ser(sb,n.left);
                ser(sb,n.right);
            }
            sb.append(']');
        }
        
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            pos=0;
            return des(data.toCharArray());
        }
        private TreeNode des(char[] data){
            pos++;
            if(data[pos]==']'){
                pos++;
                return null;
            }
            int v=0;
            while(data[pos]<='9' && data[pos]>='0'){
                v=v*10+data[pos]-'0';
                pos++;
            }
            TreeNode n = new TreeNode(v);
            n.left=des(data);
            n.right=des(data);
            pos++;
            return n;
        }
    }
    

Log in to reply
 

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