当前位置：首页 > news >正文

剑指offer题解合集——Week1day5

news 2025/7/27 21:49:52

剑指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