105. Construct Binary Tree from Preorder and Inorder Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

My Solutions：

preorder[0]是root

preorder和inorder有以下特点：

• root的左节点一定在preorder里root的下一个的位置；在inorder里root左边的位置

• root的右节点一定在preorder里root的后面的位置；在inorder里root的下一个的位置

1。recursive

class Solution {
    private int in = 0; // 记录在inorder里的index
    private int pre = 0; // 记录在preorder里的index
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, Integer.MIN_VALUE);
    }
    
    private TreeNode build(int[] preorder, int[] inorder, int stop) {
        
        if (pre >= preorder.length) return null; // 超过length，直接返回
        
        // 如果in所在的值等于stop,说明已经找到最左边的node，返回
        // 比如stop=3，inorder[0]=9，继续往下traverse。node变成9，pre=2,in=0,stop=9
        // 比如stop=9, inorder[0]=9,不需要继续，in=1
        if (inorder[in] == stop) { 
            in++;
            return null;
        }
        TreeNode node = new TreeNode(preorder[pre++]); 
        // stop是当前的node的值，比如当node=3，此时pre=1，in=0
        node.left = build(preorder, inorder, node.val); 
        node.right = build(preorder, inorder, stop);
        return node;        
    }
}

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        return helper(0, 0, inorder.length - 1, preorder, inorder);
    }
    
    public TreeNode helper(int preS, int inS, int inE, int[] preorder, int[] inorder) {
        if (preS > preorder.length - 1 || inS > inE) return null;
        
        TreeNode root = new TreeNode(preorder[preS]);
        
        // 用一个index记录root in inorder的位置
        int index = 0; 
        for (int i = inS; i <= inE; i++) {
            if (inorder[i] == root.val) index = i;
        }
        
        //the left child of root is the root's next in preorder
        // also at the root's left side in the inorder
        root.left = helper(preS + 1, inS, index - 1, preorder, inorder); 
        
        //the right child of root is the root's next in preorder
        // so that the preS = preS(index of current root in preorder) + index (skip the ones one the left of root in inorder) - inS(offset in inorder) + 1
        //and must be in the root's right side in the inorder
        root.right = helper(preS + index - inS + 1, index + 1, inE, preorder, inorder); 
        
        return root;
    }
}

2。iterative

• stack=[3]

• val = 9; 3.left=9; stack[3,9]

• val = 20; stack=[]; 3.right=20; stack=[20]

• val=15; 20.left=15; stack=[20,15]

• val=7;20.right=7;stack=[7]

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        
        // save inorder's (value : index) in a map
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) map.put(inorder[i], i); 
        
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]);
        stack.push(root);
        
        for (int i = 1; i < preorder.length; i++) {
            int value = preorder[i];
            TreeNode node = new TreeNode(value);
            
            if (map.get(value) < map.get(stack.peek().val)) { //node should be on the left of stack's top node
                stack.peek().left = node;
            } else { //node should be on the right of stack's top node
                TreeNode parent = null;
                // keep poping up node until find the root for current node 
                // && node should be on the right of stack's top node
                while (!stack.isEmpty() && map.get(value) > map.get(stack.peek().val)) { 
                    parent = stack.pop();
                }
                parent.right = node;
            }
            stack.push(node);
        }
        return root;
    }