题目描述
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3 / \ 9 20
/ \ 15 7
解题思路
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 这里有需要先创建右子树，再创建左子树的依赖关系。可以理解为在后序遍历的数组中整个数组是先存储左子树的节点，再存储右子树的节点，最后存储根节点，如果按每次选择「后序遍历的最后一个节点」为根节点，则先被构造出来的应该为右子树。
int idx = 0;
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
idx = (int)postorder.size() - 1;
return funhelper(inorder, postorder, 0, (int)inorder.size() - 1);
}
TreeNode* funhelper(vector<int>& inorder, vector<int>& postorder, int begin, int end){
if(begin > end){
return nullptr;
}
int val = postorder[idx];
TreeNode* root = new TreeNode(val);
int pos = findPos(val, inorder);
idx--;
root -> right = funhelper(inorder, postorder, pos + 1, end);
root -> left = funhelper(inorder, postorder, begin, pos - 1);
return root;
}
int findPos(int val, vector<int> inorder){
for(int i = 0; i < inorder.size(); i++){
if(inorder[i] == val){
return i;
}
}
return -1;
}
};
