106.从中序与后序遍历序列构造二叉树
力扣题目链接(opens new window)
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
- 中序遍历 inorder = [9,3,15,20,7]
- 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树：
思路
根据中序遍历和后序遍历构造二叉树的理论知识：首先由后序遍历确定根节点（从尾开始遍历），在中序遍历找到其相应的左右子节点（左中右），反复这个操作。
根据理论知识我们转换成实际操作。
- 取Postorder的最后一个元素
- 若Postorder的数组为空，则返回null
- 确定根元素在Inorder中的位置
- 开始分割
- 先分割中序
- 左毕右开
- 后分割后序
- 左闭右开
- 先分割中序
- 递归
- 返回
代码如下：
class Solution {
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(postorder.empty())return nullptr;// 当前根节点int rootValue = postorder[postorder.size()-1];TreeNode* root = new TreeNode(rootValue);// 找根节点在中序的位置int deliIndex;for(deliIndex = 0;deliIndex<inorder.size();deliIndex++){if(inorder[deliIndex] == rootValue)break;}//分割中序左右子结点vector<int> leftInorder(inorder.begin(),inorder.begin() + deliIndex);vector<int> rightInoder(inorder.begin() + deliIndex + 1, inorder.end());//分割前序左右子节点postorder.resize(postorder.size()-1);vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());root->left = buildTree(leftInorder,leftPostorder);root->right = buildTree(rightInoder,rightPostorder);return root;}
};
Tips：切割后序数组的时候，可以根据中序分割的大小进行分割，因为其大小一定是一致的。
优化
第一个优化：在找根节点分别在后序和中序中的位置时，可以使用map进行编号。
第二个优化：进行分割时，只需分割中序数组即可。
class Solution {
private:int cus_pos;unordered_map<int,int>in;
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {cus_pos=postorder.size()-1;int num=0;// 对inorder进行编号for(auto &n:inorder){in[n]=num++;}int left=0,right=inorder.size()-1;return dis(left,right,inorder,postorder);}TreeNode* dis(int left,int right,vector<int>& inorder, vector<int>& postorder){if(left>right)return nullptr;int root_val=postorder[cus_pos--];int index=in[root_val];TreeNode* p=new TreeNode(root_val);// 分割数组p->right=dis(index+1,right,inorder,postorder);p->left=dis(left,index-1,inorder,postorder);return p;}
};r,postorder);p->left=dis(left,index-1,inorder,postorder);return p;}
};
