网站综合开发怎么做,台州电子商务网站建设,企业网络营销策略研究,深圳网站网络推广公司106.从中序与后序遍历序列构造二叉树
力扣题目链接(opens new window)
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如#xff0c;给出
中序遍历 inorder [9,3,15,20,7]后序遍历 postorder [9,15,7,20,3] 返回如下的二叉树给出
中序遍历 inorder [9,3,15,20,7]后序遍历 postorder [9,15,7,20,3] 返回如下的二叉树 思路
根据中序遍历和后序遍历构造二叉树的理论知识首先由后序遍历确定根节点从尾开始遍历在中序遍历找到其相应的左右子节点左中右反复这个操作。
根据理论知识我们转换成实际操作。
取Postorder的最后一个元素 若Postorder的数组为空则返回null 确定根元素在Inorder中的位置开始分割 先分割中序 左毕右开 后分割后序 左闭右开 递归返回
代码如下
class Solution {
public:TreeNode* buildTree(vectorint inorder, vectorint postorder) {if(postorder.empty())return nullptr;// 当前根节点int rootValue postorder[postorder.size()-1];TreeNode* root new TreeNode(rootValue);// 找根节点在中序的位置int deliIndex;for(deliIndex 0;deliIndexinorder.size();deliIndex){if(inorder[deliIndex] rootValue)break;}//分割中序左右子结点vectorint leftInorder(inorder.begin(),inorder.begin() deliIndex);vectorint rightInoder(inorder.begin() deliIndex 1, inorder.end());//分割前序左右子节点postorder.resize(postorder.size()-1);vectorint leftPostorder(postorder.begin(), postorder.begin() leftInorder.size());vectorint 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_mapint,intin;
public:TreeNode* buildTree(vectorint inorder, vectorint postorder) {cus_pospostorder.size()-1;int num0;// 对inorder进行编号for(auto n:inorder){in[n]num;}int left0,rightinorder.size()-1;return dis(left,right,inorder,postorder);}TreeNode* dis(int left,int right,vectorint inorder, vectorint postorder){if(leftright)return nullptr;int root_valpostorder[cus_pos--];int indexin[root_val];TreeNode* pnew TreeNode(root_val);// 分割数组p-rightdis(index1,right,inorder,postorder);p-leftdis(left,index-1,inorder,postorder);return p;}
};r,postorder);p-leftdis(left,index-1,inorder,postorder);return p;}
};
