Here is the iterative solution in Java


  • 12
    O
    public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (inorder.length==0) return null; 
            Stack<TreeNode> stack = new Stack<TreeNode>(); 
            TreeNode root = new TreeNode(Integer.MIN_VALUE);
            stack.push(root); 
            int i=0, j=0;
            TreeNode node = null; 
            TreeNode cur = root; 
            while (j<inorder.length){
                if (stack.peek().val == inorder[j]){
                    node = stack.pop(); 
                    j++; 
                }
                else if (node!=null){
                    cur = new TreeNode(preorder[i]); 
                    node.right = cur;
                    node=null; 
                    stack.push(cur); 
                    i++; 
                }
                else {
                    cur = new TreeNode(preorder[i]); 
                    stack.peek().left = cur; 
                    stack.push(cur);
                    i++; 
                }
            }
            return root.left; 
        }

  • 0
    X

    So the root is actually a fake root, like a dummy node


Log in to reply
 

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