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);
}
};
