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

Thoughts:

1. Given preorder root preorder[preStart]: Find the corresponding index in the inorder array i, then [inStart ... i - 1] is the left tree, and [i + 1, inEnd] is the right tree. Base case: either preStart out of right bounds or inStart > inEnd.

2. Iterative Solution: from gpraveenkumar's post:

   1. Keep pushing the nodes from the preorder into a stack (and keep making the tree by adding nodes to the left of the previous node) until the top of the stack matches the inorder.

   2. At this point, pop the top of the stack until the top does not equal inorder (keep a flag to note that you have made a pop).

   3. Repeat 1 and 2 until preorder is empty. The key point is that whenever the flag is set, insert a node to the right and reset the flag.

Code: Recursive: T:(NlogN),

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(0,0,inorder.length - 1, preorder, inorder);
    }

    private TreeNode build(int preStart, int inStart, int inEnd, int [] preorder, int [] inorder){
        if(preStart > preorder.length - 1 || inStart > inEnd) return null;

        TreeNode root = new TreeNode(preorder[preStart]);
        int split = 0;
        for(int i = inStart; i <= inEnd; i++ ){
            if(inorder[i] == preorder[preStart])  split = i;
        }

        root.left = build(preStart + 1, inStart, split - 1, preorder, inorder);
        root.right = build(preStart + 1 + split - inStart, split + 1, inEnd, preorder, inorder);

        return root;
    }
}

Code: Iterative: T: O()

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

         if(preorder.size()==0)
             return NULL;

         stack<int> s; stack<TreeNode *> st;
         TreeNode *t,*r,*root;
         int i,j,f; f=i=j=0;
         s.push(preorder[i]);

         root = new TreeNode(preorder[i]);
         st.push(root); t = root;i++;

         while(i<preorder.size()) {
             if(!st.empty() && st.top()->val==inorder[j]){
                 t = st.top();
                 st.pop();
                 s.pop();
                 f = 1;
                 j++;
             }
             else {
                 if(f==0) {
                     s.push(preorder[i]);
                     t -> left = new TreeNode(preorder[i]);
                     t = t -> left;
                     st.push(t);
                     i++;
                 }
                 else {
                     f = 0;
                     s.push(preorder[i]);
                     t -> right = new TreeNode(preorder[i]);
                     t = t -> right;
                     st.push(t);
                     i++;
                 }
             }
         }

         return root;
     }
};