网站建设导航,滁州注册公司流程和费用,做视频最全的网站,企业网站功能清单剑指offerWeek1
周五#xff1a;重建二叉树
题目链接#xff1a;重建二叉树
输入一棵二叉树前序遍历和中序遍历的结果#xff0c;请重建该二叉树。注意:二叉树中每个节点的值都互不相同#xff1b;
输入的前序遍历和中序遍历一定合法#xff1b;
数据范围
树中节点数量…剑指offerWeek1
周五重建二叉树
题目链接重建二叉树
输入一棵二叉树前序遍历和中序遍历的结果请重建该二叉树。注意:二叉树中每个节点的值都互不相同
输入的前序遍历和中序遍历一定合法
数据范围
树中节点数量范围 [0,100]
。样例
给定
前序遍历是[3, 9, 20, 15, 7]
中序遍历是[9, 3, 15, 20, 7]返回[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示3/ \9 20/ \15 7AC代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:unordered_mapint, int map;TreeNode* buildTree(vectorint preorder, vectorint inorder) {for (int i 0; i inorder.size(); i ) map[inorder[i]] i;return dfs(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);}TreeNode* dfs(vectorint preorder, vectorint inorder, int pl, int pr, int il, int ir){if (pl pr) return nullptr;auto node new TreeNode(preorder[pl]);int k map[node-val];node-left dfs(preorder, inorder, pl 1, pl k - il, il, k - 1);node-right dfs(preorder, inorder, pl k - il 1, pr, k 1, ir);return node;}
};思路
整体思路
要时刻牢记前序遍历、中序遍历的特点
前序第一个遍历的一定是根节点
中序遍历在根节点的左边一定是左子树右边则是右子树那么两个性质结合可以从前序遍历中找到根节点
然后再从中序遍历中根据根节点划分左右子树
在左右子树中递归以上步骤则可以重建二叉树本题还有一个难点
当知道根节点以后如何划分左右子树
别说什么哎呀中序遍历知道根节点左边的不就是左子树吗
注意我这里指的是在前序遍历的数集中划分左右子树
这里是利用左右子树区间长度相等得出区间边界代码思路
利用map构造出中序遍历的值能索引到值对应的下标为了更好的找到根节点递归递归的条件是前序遍历集存在 构造根节点找到根节点的下标值在左子树中递归 前序遍历区间第一个节点是pl也是根节点因此左子树从pl 1开始左子树的右端点待定中序遍历的区间左端点为il右端点为根节点的索引值 - 1 在右子树中递归 右子树 前序遍历区间左端点待定右端点显然是pr中序遍历的区间左端点为根节点的索引值 1右端点ir 返回根节点
以上有两个待定的端点也是难点
这里需要利用性质左右子树区间长度相等得出区间边界
记根节点下标为k
由于中序遍历中左子树区间为[il, k - 1]
前序遍历[pl 1, 待定]
记前序遍历区间的右端点为x
则有
x - pl - 1 1 k - 1 - il 1
则可以解出x k - il pl
则前序遍历中右子树的左端点显然为这个x 1
部分模拟
前序遍历是[3, 9, 20, 15, 7] 中序遍历是[9, 3, 15, 20, 7]
前序遍历第一个节点为根节点显然为3从中序遍历中得到3因此9是左子树15, 20, 7是右子树左子树已经确定 右子树中继续递归即可例如右子树的根为20前序遍历中得出
