Non-recursive solution


  • 0
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            
            if (preorder==null || preorder.length==0) {
                return null;
            }
            
            Stack<TreeNode> stack = new Stack<>();
            
            int len = preorder.length;
            int i1 = 0;
            int i2 = 0;
            
            TreeNode root = new TreeNode(preorder[i1++]);
            stack.push(root);
            
            for (; i1<len; i1++) {
                
                TreeNode curr = stack.peek();
                
                if (curr.val!=inorder[i2]) {
                    TreeNode left = new TreeNode(preorder[i1]);
                    curr.left = left;
                    stack.push(left);
                } else {
                    while (!stack.isEmpty() && stack.peek().val==inorder[i2]) {
                        i2++;
                        curr = stack.pop();
                    }
                    TreeNode right = new TreeNode(preorder[i1]);
                    curr.right = right;
                    stack.push(right);
                }
                
            }
            
            return root;
            
            
        }
        
    }
    

  • 0
    C

    This is awesome!


Log in to reply
 

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