Java concise preorder traversal to serialize using stack, deserialize using binary search


  • 0
    Y

    To serialize, I used the same method as in 144 Binary Tree Preorder Traversal, and separate every node by space.
    To deserialize, I used binary search and recursion to build the tree.

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if(root == null) return "";
            Stack<TreeNode> stack = new Stack();
            stack.push(root);
            StringBuilder sb = new StringBuilder();
            while(!stack.isEmpty()) {
                TreeNode cur = stack.pop();
                sb.append(cur.val + " ");
                if(cur.right != null)
                    stack.push(cur.right);
                if(cur.left != null)
                    stack.push(cur.left);
            }
            System.out.println(sb.substring(0, sb.length()-1));
            return sb.substring(0, sb.length()-1);
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if(data.length() == 0) return null;
            String[] nodes = data.split(" ");
            return helper(nodes, 0, nodes.length-1);
        }
        
        public TreeNode helper(String[] nodes, int start, int end) {
            if(start > end) return null;
            TreeNode root = new TreeNode(Integer.valueOf(nodes[start]));
            if(start == end) return root;
            int left = start + 1, right = end + 1;
            while(left < right) {
                int mid = (right - left)/2 + left;
                if(Integer.valueOf(nodes[mid]) < root.val) left = mid + 1;
                else right = mid;
            }
            root.left = helper(nodes, start+1, right-1);
            root.right = helper(nodes, right, end);
            return root;
        }
    

Log in to reply
 

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