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

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

---

题目链接：106. 从中序与后序遍历序列构造二叉树

代码如下：

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return tree(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);
    }

    TreeNode* tree(vector<int>& inorder,int inl,int inr, vector<int>& postorder,int postl,int postr)
    {
        if(postl>postr)
            return nullptr;

        TreeNode *root=new TreeNode(postorder[postr],nullptr,nullptr);

        int index = inl;
        while (inorder[index] != root->val)
            index++;
        int llen = index - inl;
        root->left = tree( inorder, inl, index - 1,postorder, postl, postl + llen - 1);
        root->right = tree(inorder, index + 1, inr,postorder, postl + llen, postr - 1);
        return root;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23