力扣题目链接(opens new window)
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
- 中序遍历 inorder = [9,3,15,20,7]
- 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树：
class Solution {
public:TreeNode* dfs(vector<int>& inorder, vector<int>& postorder){if(postorder.size() == 0) return nullptr;int tmp = postorder.back();TreeNode* root = new TreeNode(tmp);if(postorder.size() == 1) return root;//确定分割点int index;for(index = 0;index < inorder.size();index++){if(inorder[index] == tmp) break;}//分割,左右中vector<int> leftin(inorder.begin(),inorder.begin()+index);vector<int> rightin(inorder.begin()+index+1,inorder.end());postorder.resize(postorder.size()-1);//左右后vector<int>leftpost(postorder.begin(),postorder.begin()+leftin.size());vector<int>rightpost(postorder.begin()+leftin.size(),postorder.end());root->left = dfs(leftin,leftpost);root->right = dfs(rightin,rightpost);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {//也可以采用数组下标，来减少空间复杂度。if(inorder.size() == 0 || postorder.size() == 0) return nullptr;return dfs(inorder,postorder);}
};//维护边界点（动态更新边界）。一般方法，可减少空间复杂度
class Solution {
public:TreeNode* dfs(vector<int>& inorder,int inbeg,int inend,vector<int>& postorder,int postbeg,int postend){if(postend == postbeg) return nullptr;int tmp = postorder[postend-1];TreeNode* root = new TreeNode(tmp);if(postend - postbeg == 1) return root;//分割点int index;for(index = inbeg;index < inend;index++){if(inorder[index] == tmp) break;}//中int leftinbeg = inbeg;int leftinend = index;int rightinbeg = leftinend+1;int rightinend = inend;//后int leftpostbeg = postbeg;int leftpostend = postbeg+leftinend-leftinbeg;int rightpostbeg = leftpostend;int rightpostend = postend-1;root->left = dfs(inorder,leftinbeg,leftinend,postorder,leftpostbeg,leftpostend);root->right = dfs(inorder,rightinbeg,rightinend,postorder,rightpostbeg,rightpostend);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(inorder.size() == 0 || postorder.size() == 0) return nullptr;return dfs(inorder,0,inorder.size(),postorder,0,postorder.size());}
};
