Java Solution using recursion beats 96%


  • 0
    H
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Codec {
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if(root == null)
                return "";
            return "(" + serialize(root.left) + ")" + root.val + "(" + serialize(root.right) + ")"; 
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.length() == 0)
                return null;
            Item res = deserialize(data, -1);
            return res.node;
        }
        
        private Item deserialize(String data, int start) {
            char next = data.charAt(start + 1);
            if (next == '(') {
                //
                Item left = deserialize(data, start + 1);
                int rootIdx = left.end + 1;
                int i = rootIdx;
                while (i < data.length() && data.charAt(i) != '(')
                    ++i;
                TreeNode root = new TreeNode(Integer.parseInt(data.substring(rootIdx, i)));
                root.left = left.node;
                Item right = deserialize(data, i);
                root.right = right.node;
                return new Item(root, right.end + 1);
            } else {
                return new Item(null, start + 1);
            } 
        }
        
        class Item {
            int end;
            TreeNode node;
            public Item(TreeNode node, int end) {
                this.end = end;
                this.node = node;
            }
        }
    }
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec = new Codec();
    // codec.deserialize(codec.serialize(root));

Log in to reply
 

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