剑指offer题解合集——Week1day5
2023-12-21 06:38:15
剑指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 7
AC代码
/**
* 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_map<int, int> map;
TreeNode* buildTree(vector<int>& preorder, vector<int>& 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(vector<int>& preorder, vector<int>& 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(前序遍历中得出)
文章来源:https://blog.csdn.net/qq_51931826/article/details/135120386
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!