0106. 从中序与后序遍历序列构造二叉树.md

106. 从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

3

/
9 20 /
15 7

code

/**
 * 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>& inorder, vector<int>& postorder) {
        int len = inorder.size();
        return buildTree(inorder, 0, len-1, postorder, 0, len-1);
    }
    TreeNode* buildTree(vector<int>& inorder, int l1, int r1, vector<int>& postorder, int l2, int r2){
        if(l1 > r1) return NULL;
        int v = postorder[r2];
        TreeNode* root = new TreeNode(v);
        int tmp = 0;
        while(inorder[l1 + tmp] != v) {tmp++;}
        root->left = buildTree(inorder, l1, l1+tmp-1, postorder, l2, l2+tmp-1);
        root->right = buildTree(inorder, l1+tmp+1, r1, postorder, l2+tmp, r2-1);
        return root;
    }
};