[leetcode] 106. Construct Binary

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

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

解题思路：
本题和105. Construct Binary Tree from Preorder and Ignorer Traversal类似，只是把前序遍历数组改为后续遍历数组，要求我们在给定二叉树的后续遍历数组和中序遍历数组的情况下，构造二叉树。基本思路如下：

• 后续遍历数组的最后一个数preorder[n]就是二叉树的根节点
• 遍历中序数组，找到根节点，假设为inorder[i]
• 假定数组的长度为n, 则inorder[0]...inorder[i-1]构成左子树，inorder[i+1]...inorder[n]构成右子树。
• 重复以上过程，即可构造二叉树。

具体代码如下：

class Solution {
public:
    TreeNode* buildTreeHelper(int postEnd, int inStart, int inEnd, vector<int>& inorder, vector<int>& postorder)
    {
        if(postEnd < 0 || inStart > inEnd) return NULL;
        TreeNode * root = new TreeNode(postorder[postEnd]);
        int index = 0;
        for(int i = 0; i < inorder.size(); ++i)
        {
            if(postorder[postEnd] == inorder[i])
                index = i;
        }
        root->left = buildTreeHelper(postEnd - (inEnd - index) - 1, inStart, index - 1, inorder, postorder);
        root->right = buildTreeHelper(postEnd - 1, index + 1, inEnd,inorder,postorder);
        return root;
    }
    
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return buildTreeHelper(postorder.size() - 1, 0, inorder.size() - 1, inorder, postorder);
    }
};