[剑指Offer]7-重建二叉树

时间:2023-03-08 16:53:20
[剑指Offer]7-重建二叉树

链接

https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题意

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

解题思路

递归。

其中,在找前序遍历的左右子树分割点时,用中序遍历的左右子树节点数直接找。

注意,只有各节点取值均不相同时,才能重建二叉树。

相关

用一个vector给另一个vector赋值,用vector的构造函数vector<int> rightVin(it+1,vin.end());

获取vector首节点vec.front()

代码

class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.empty()||vin.empty()||pre.size()!=vin.size()){
return nullptr;
} TreeNode* pRoot=new TreeNode(pre.front());
if(pre.size()!=1){
vector<int>::iterator it=find(vin.begin(),vin.end(),pre.front());
vector<int> leftVin(vin.begin(),it);
vector<int> rightVin(it+1,vin.end()); vector<int>::iterator splitIt=pre.begin()+leftVin.size()+1;
vector<int> leftPre(pre.begin()+1,splitIt);
vector<int> rightPre(splitIt,pre.end()); pRoot->left=reConstructBinaryTree(leftPre,leftVin);
pRoot->right=reConstructBinaryTree(rightPre,rightVin);
}
return pRoot;
}
};