剑指 Offer 07. 重建二叉树
本问题对应的 leetcode 原文链接：剑指 Offer 07. 重建二叉树
本次对应打卡问题：【二叉树专题】剑指 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
解题思路
视频讲解直达： 本题视频讲解
代码实现
Map< Integer, Integer > map = new HashMap();
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || preorder.length <= 0){
return null;
}
// 简历中序遍历数组的映射（就是为了快速求出某个元素的下标）
for(int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
TreeNode root = f(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
return root;
}
TreeNode f(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2) {
// 前序遍历或者中序遍历为空时，表示这棵树不存在，直接返回 null
if( l1 > r1 || l2 > r2){
return null;
}
// 根节点
TreeNode root = new TreeNode(preorder[l1]);
// 根节点在中序遍历中的下标
int i = map.get(preorder[l1]);
// 递归求解
root.left = f(preorder, l1 + 1, l1 + (i - l2), inorder, l2, i - 1);
root.right = f(preorder, l1 + (i - l2) + 1, r1, inorder, i + 1, r2);
return root;
}
- 时间复杂度 O(N) ： 其中 NN 为树的节点数量。初始化 HashMap 需遍历 inorder ，占用 O(N) 。递归共建立 NN 个节点，每层递归中的节点建立、搜索操作占用 O(1) ，因此使用 O(N) 时间。
- 空间复杂度 O(N) ： HashMap 使用 O(N) 额外空间；最差情况下（输入二叉树为链表时），递归深度达到 N ，占用 O(N)的栈帧空间；因此总共使用 O(N) 空间。