【LeetCode】剑指 Offer 07. 重建二叉树 p62 -- Java Version

题目链接：https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/

1. 题目介绍（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

2. 题解

2.1 递归

时间复杂度：O(n)，空间复杂度：O(n)

但下列解法仅适用于 “无重复节点值” 的二叉树。
原因在于我们使用了HashMap来存储中序遍历的值和索引，也就默认了它的值是唯一的。

前序遍历性质： 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序。
中序遍历性质： 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。
这里的递归用到了分治的思想，通过前序遍历，我们很容易就可以找到根节点，然后我们就可以拿着这个根节点的值去中序遍历中找，此时中序遍历根节点的左边就属于当前根的左子树，右边就属于当前根的右子树，以此类推…

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {// 1. 定义前序遍历索引，用于定位当前前序遍历所在的位置int preorderIndex = 0;// 2. 创建一个哈希表，用于存储中序遍历节点的位置//    后续想要查找元素，就可以将时间复杂度降为O(1)HashMap<Integer,Integer> inorderMap = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {// 3. 循环遍历，依次将inorder元素添加到哈希表中for (int i = 0; i < inorder.length; i++){inorderMap.put(inorder[i],i);}//  8. 最后返回根节点return arrayToTree(preorder,0,preorder.length-1);}public TreeNode arrayToTree(int[] preorder,int start, int end){// 4. 递归的出口，如果左边位置移动到超过右边，表示走完了，返回空if (start > end) return null;// 5. 创建一个TreeNode对象，用来保存当前的根节点TreeNode root = new TreeNode();root.val = preorder[preorderIndex++];// 6. 递归找左子树、递归找右子树root.left = arrayToTree(preorder,start,inorderMap.get(root.val)-1);      root.right = arrayToTree(preorder,inorderMap.get(root.val)+1,end);// 7. 当前递归结束，返回当前节点return root;}
}

此外还有很多其它解法，例如通过迭代加辅助栈的方法来求解，具体内容可参考[2] 重建二叉树（力扣官方题解）.

3. 可参考

[1] 剑指 Offer 07. 重建二叉树（分治算法，清晰图解）
[2] 重建二叉树（力扣官方题解）
[3] 【LeetCode】No.105. Construct Binary Tree from Preorder and Inorder Traversal – Java Version （重复）