题目链接：Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

这道题的要求是通过二叉树的中序遍历和后序遍历结果构建二叉树。

和Construct Binary Tree from Preorder and Inorder Traversal类似的思路：

二叉树中序遍历，根节点在中间，左侧是左子树的节点，右侧是右子树的节点；二叉树后序遍历，前面是左子树、右子数的节点，然后根节点在最后面。由此可以确定，后序遍历的最后节点就是根节点，而中序遍历中和后序遍历的最后节点相同的同样为根节点，同时左侧即为左子树，右侧即为右子数。至于左右子树的情况，可以通过递归生成。

例如：

二叉树为：
        1
       / \
      2   3
     / \   \
    4   5   6
    
中序遍历：
    4 -> 2 -> 5 -> 1 -> 3 -> 6
    |---------|    |    |----|
       左子树    根节点 右子数

后序遍历：
    4 -> 5 -> 2 -> 6 -> 3 -> 1
    |---------|    |----|    |
       左子树      右子数  根节点

分别在中序遍历和后序遍历中找到了根节点和左右子树，接下来就可以构建这棵树了。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution
{
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
    {
        return buildTree(inorder, 0, inorder.size() - 1, 
                         postorder, 0, postorder.size() - 1);
    }
private:
    // inorder：中序遍历的序列；il和ir：中序遍历序列中树的左右端点；
    // postorder：后序遍历的序列；pl和pr：后序遍历序列中树的左右端点。
    TreeNode *buildTree(vector<int> &inorder, int il, int ir, 
                        vector<int> &postorder, int pl, int pr)
    {
        if(il > ir && pl > pr)
            return NULL;
        
        int m;
        // 在中序遍历序列中找到根节点位置
        for(m = il; m <= ir && postorder[pr] != inorder[m]; ++ m);
        
        TreeNode *t = new TreeNode(postorder[pr]);
        t->left = buildTree(inorder, il, m - 1, 
                            postorder, pl, pl + m - il - 1);
        t->right = buildTree(inorder, m + 1, ir, 
                             postorder, pl + m - il, pr - 1);
        return t;
    }
};