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

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

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

例如，给出

中序遍历 

1
inorder = [9,3,15,20,7]

后序遍历 

1
postorder = [9,15,7,20,3]

返回如下的二叉树：

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
TreeNode* makeTree(vector<int>& postorder, int& postindex, vector<int>& inorder,int left, int right){
        if(left <= right){
            for(int i = 0; i < inorder.size(); i++){
                if(postorder[postindex] == inorder[i]){

                    TreeNode* root = new TreeNode(postorder[postindex--]);
                    root->right = makeTree(postorder,postindex,inorder,i+1,right);
                    root->left = makeTree(postorder,postindex,inorder,left,i-1);  
                    return root;
                }
            }
        }
        return NULL;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int postindex = postorder.size()-1;
        return makeTree(postorder,postindex,inorder,0,inorder.size()-1);
    }

思路：

根据后序遍历的特点，每棵子树的根节点总是最后遍历到。

所以用一个按引用传递的指针指向后序数组的末尾，用该值在中序数组中查找，并将该值当做当前树的根节点。

该值位置的左边为以该节点为根节点的左子树的范围，位置右边为右子树的范围，然后不断更新这个范围，递归下去即可，注意边界值。