(树) 剑指 Offer 07. 重建二叉树 ——【Leetcode每日一题】

❓剑指 Offer 07. 重建二叉树

难度：中等

输入某二叉树的 前序遍历 和 中序遍历 的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制：

• 0 <= 节点个数 <= 5000

注意：本题与 105. 从前序与中序遍历序列构造二叉树 相同。

💡思路：递归

二叉树前序遍历的顺序为：

• 先遍历根节点；
  • 随后递归地遍历左子树
  • 最后递归地遍历右子树

二叉树中序遍历的顺序为：

• 先递归地遍历左子树；
• 随后遍历根节点；
• 最后递归地遍历右子树

在「递归」地遍历某个子树的过程中，我们也是将这颗子树看成一颗全新的树，按照上述的顺序进行遍历。挖掘「前序遍历」和「中序遍历」的性质，我们就可以得出本题的做法。

前序遍历的第一个值为根节点的值，使用这个值将 中序遍历 结果分成两部分：

• 左部分 为树的左子树中序遍历结果；
• 右部分 为树的右子树中序遍历的结果；
• 然后分别对左右子树递归地求解。

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。

• 由于同一颗子树的 前序遍历 和 中序遍历 的 长度显然是相同 的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。
• 这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

🍁代码：(C++、Java)

C++

/*** 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 {
private:unordered_map<int, int> index;//缓存中序遍历数组每个值对应的索引TreeNode* myBuildTree(const vector<int> preorder, int preL, int preR, int inL){if(preL > preR) return nullptr;// 前序遍历中的第一个节点就是根节点TreeNode* root = new TreeNode(preorder[preL]);// 在中序遍历中定位根节点int idx = index[root->val];// 得到左子树中的节点数目int len = idx - inL;root->left = myBuildTree(preorder, preL + 1, preL + len, inL);root->right = myBuildTree(preorder, preL + len + 1, preR, inL + len + 1);return root;}public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {for(int i = 0; i < preorder.size(); i++){index[inorder[i]] = i;}return myBuildTree(preorder, 0, preorder.size() - 1, 0);}
};

Java

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {private Map<Integer, Integer> index = new HashMap<>();//缓存中序遍历数组每个值对应的索引public TreeNode buildTree(int[] preorder, int[] inorder) {for (int i = 0; i < preorder.length; i++){index.put(inorder[i], i);}return myBuildTree(preorder, 0, preorder.length - 1, 0);}private TreeNode myBuildTree(int[] preorder, int preL, int preR, int inL){if(preL > preR) return null;// 前序遍历中的第一个节点就是根节点TreeNode root = new TreeNode(preorder[preL]);// 在中序遍历中定位根节点int idx = index.get(root.val);// 得到左子树中的节点数目int len = idx - inL;root.left = myBuildTree(preorder, preL + 1, preL + len, inL);root.right = myBuildTree(preorder, preL + len + 1, preR, inL + len + 1);return root;}
}

🚀 运行结果：

🕔 复杂度分析：

• 时间复杂度：$O(n)$，其中 n 是树中的节点个数。
• 空间复杂度：$O(n)$，除去返回的答案需要的 $O(n)$ 空间之外，我们还需要使用 $O(n)$ 的空间存储哈希映射，以及 $O(h)$（其中 h 是树的高度）的空间表示递归时栈空间。这里 h < n，所以总空间复杂度为 $O(n)$。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我LeetCode主页 / CSDN—力扣专栏，每日更新！

注： 如有不足，欢迎指正！