根据两个traversal恢复二叉树

已知前序和中序遍历：

递归版本：

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int len = preorder.size();
        return buildCore(preorder, 0, inorder, 0, len);
    }
    TreeNode* buildCore(vector<int>& preorder, int start1, vector<int>& inorder, int start2, int num) {
        if(num == 0) return NULL;
        TreeNode* root = new TreeNode(preorder[start1]);
        if(num == 1) return root;
        int leftnum = 0, i = start2;
        //find in the inorder
        for(; i<start2 + num; i++){
            if(inorder[i] != preorder[start1])
                leftnum++;
            else break;
        }
        root -> left = buildCore(preorder, start1 + 1, inorder, start2, leftnum);
        root -> right = buildCore(preorder, start1 + leftnum + 1, inorder, i + 1, num - leftnum - 1);
        return root;
    }

非递归版本：

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int num = preorder.size();
        if(num == 0) return NULL;
        stack<TreeNode*> st;
        TreeNode* root = new TreeNode(preorder[0]), *cur = root;
        for(int i = 1, j = 0; i<num; i++){
            if(inorder[j] == cur -> val){
                j++;
                while(!st.empty() && st.top() -> val == inorder[j]){
                    cur = st.top();
                    st.pop();
                    j++;
                }
                cur -> right = new TreeNode(preorder[i]);
                cur = cur -> right;
            }
            else{
                cur -> left = new TreeNode(preorder[i]);
                st.push(cur);
                cur = cur -> left;
            }
        }
        return root;
    }

已知后序和中序遍历：
非递归：

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int len = inorder.size();
        if(len == 0) return NULL;
        stack<TreeNode*> st;
        TreeNode* root = new TreeNode(postorder[len-1]), *cur = root;
        st.push(root);
        for(int i = len-2, j = len-1; i>=0; i--){
            if(cur -> val != inorder[j]){
                cur -> right = new TreeNode(postorder[i]);
                st.push(cur);
                cur = cur -> right;
            }
            else{
                j--;
                while(!st.empty() && st.top() -> val == inorder[j]){
                    cur = st.top();
                    st.pop();
                    j--;
                }
                cur -> left = new TreeNode(postorder[i]);
                cur = cur -> left;
            }
        }
        return root;
    }