Construct Binary Tree from Preorder and Inorder Traversal (3 solutions)

Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

This problem has 3 kinds of solutions.

1. Time complexity O(N^2)

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        if (preorder.size()==0) return NULL;
        else
        return helper(preorder, inorder, 0, inorder.size()-1,0);
    }
   
    TreeNode *helper(vector<int> &preorder, vector<int> &inorder, int start, int end, int rIdx)
    {
        if (start>end)
         return NULL;
        TreeNode *r = new TreeNode(preorder[rIdx]);
        int mid=0;
        for (int i=start; i<=end; i++)
        {
            if (inorder[i]==preorder[rIdx])
            {
                mid = i;
                break;
            }
        }
       
        r->left = helper(preorder,inorder,start,mid-1,rIdx+1);
        r->right = helper(preorder, inorder,mid+1,end,rIdx+mid-start+1);
       
        return r;
    }
};


2. Using a hashtable to hash the index of inorder traversal will speed this up to O(N)
http://leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        if (preorder.size()==0) return NULL;
        else
        {
            unordered_map<int, int> idxMap;
            int len = inorder.size();
           
            for (int i=0; i<len; i++)
            {
               idxMap[inorder[i]]=i;
            }
            return helper(preorder, inorder, 0, inorder.size()-1,0, idxMap);
        }
    }
   
    TreeNode *helper(vector<int> &preorder, vector<int> &inorder, int start, int end, int rIdx, unordered_map<int, int> &map)
    {
        if (start>end)
         return NULL;
        TreeNode *r = new TreeNode(preorder[rIdx]);
        int mid=map[preorder[rIdx]];
       
        r->left = helper(preorder,inorder,start,mid-1,rIdx+1, map);
        r->right = helper(preorder, inorder,mid+1,end,rIdx+mid-start+1, map);
       
        return r;
    }
};

3. The iterative solution that has O(N) time complexity
Idea:
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 (Use the popped node to note that you have made a pop).

3) Repeat 1 and 2 until preorder is empty. The key point is that whenever
the the popped node is NULL, insert a node to the right of the popped Node and reset popped Node to be NULL.

算法很巧妙。
我的理解是根据preorder inorder的基本原理，
1）能够保证左子树都入栈
2）3）中pop出来的node的左子树都在栈下面压着，所以在preorder里面的下一个肯定
是right child。
除了第一个元素外，其他每个元素进出栈一次，而且i,j各扫描pre,in一次。

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        int i=0,j=0;
        TreeNode *root = new TreeNode(INT_MAX);
        TreeNode *pp = NULL, *ptr = root;
        stack<TreeNode *> st;
        st.push(root);
       
        while(j<inorder.size())
        {
            if (st.top()->val==inorder[j])
            {
                pp=st.top();
                st.pop();
                j++;
            }
            else if (pp){
                ptr = new TreeNode(preorder[i]);
                pp->right = ptr;
                pp=NULL;
                st.push(ptr);
                i++;
            }
            else {
                ptr=new TreeNode(preorder[i]);
                st.top()->left=ptr;
                st.push(ptr);
                i++;
            }
        }
        ptr=root->left;delete root;
        return ptr;       
    }
};