2021/3/24 剑指 Offer 07. 重建二叉树（未解决）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了2021/3/24 剑指 Offer 07. 重建二叉树（未解决），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2808字，纯文字阅读大概需要5分钟。
内容图文
https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-by-leetcode-s/
前言
二叉树前序遍历的顺序为：先遍历根节点；随后递归地遍历左子树；最后递归地遍历右子树。
二叉树中序遍历的顺序为：先递归地遍历左子树；随后遍历根节点；最后递归地遍历右子树。
在「递归」地遍历某个子树的过程中，我们也是将这颗子树看成一颗全新的树，按照上述的顺序进行遍历。挖掘「前序遍历」和「中序遍历」的性质，我们就可以得出本题的做法。
方法一：递归
思路
对于任意一颗树而言，前序遍历的形式总是[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]即根节点总是前序遍历中的第一个节点。
而中序遍历的形式总是[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。
这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。
细节
在中序遍历中对根节点进行定位时，一种简单的方法是直接扫描整个中序遍历的结果并找出根节点，但这样做的时间复杂度较高。我们可以考虑使用哈希表来帮助我们快速地定位根节点。对于哈希映射中的每个键值对，键表示一个元素（节点的值），值表示其在中序遍历中的出现位置。
在构造二叉树的过程之前，我们可以对中序遍历的列表进行一遍扫描，就可以构造出这个哈希映射。在此后构造二叉树的过程中，我们就只需要 O(1)的时间对根节点进行定位了。
/*
算法思想：使用前中序递归建树
*/
class Solution {
public:
unordered_map<int, int> in_map; //快速找到 （前序中找的根）在中序中的位置，便于对中序序列进行左右子树的划分
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
{
for(int i = 0; i < inorder.size(); i++) //<中序序列, 索引>
in_map[inorder[i]] = i;
return find_par_build(preorder, inorder, 0, 0, inorder.size() - 1);
//传入的参数列表：（前序序列，中序序列，在前序序列中找到的根节点，中序左边界，中序右边界）
}
TreeNode* find_par_build(vector<int>& preorder, vector<int>& inorder, int pre_root, int in_left_bound, int in_right_bound)
{
if(in_left_bound > in_right_bound) //子树中序遍历为空，说明已经越过叶子节点，此时返回 null
return NULL;
TreeNode* root = new TreeNode(preorder[pre_root]); //在前序序列中找到根节点
int in_root = in_map[preorder[pre_root]]; //定位根节点在中序序列中的位置，此时in_root左边是左子树，右边是右子树
//找左子树的根：
root->left = find_par_build(preorder, inorder, pre_root + 1, in_left_bound, in_root -1);
//左子树在前序中的根节点位于：pre_root+1； 左子树在中序中的边界：[in_left_bound,in_root-1]
//找右子树的根
root->right = find_par_build(preorder, inorder, pre_root + (in_root - in_left_bound + 1), in_root + 1, in_right_bound);
// 右子树在前序中的根节点位于：根节点+（左子树长度+1）；右子树在中序中的边界：[in_root+1,in_right_bound]
return root;
}
};
内容总结
以上是互联网集市为您收集整理的2021/3/24 剑指 Offer 07. 重建二叉树（未解决）全部内容，希望文章能够帮你解决2021/3/24 剑指 Offer 07. 重建二叉树（未解决）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。