【Java题解】剑指 Offer 07. 重建二叉树

【Java题解】剑指 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

方法一：

1. 用二叉树遍历的性质，前序遍历是：根 左 右，中序遍历是：左 根 右。
2. 那么根据前序遍历，如果在中序遍历中找到了相应的节点，那么在中序遍历中，该节点前面就是该根节点的左子树上的所有节点，右边所有节点就是该根节点右子树上的所有节点。
3. 然后使用递归，去找到所有节点的左右子树，就能构建出一颗二叉树了。

代码：

class Solution {
    // 方法：在中序遍历数组中找到前序遍历的值，在中序遍历列表中，该值左边就是左子树上的值，右边就是右子树上的值。
    // 使用递归来寻找全部节点的左右子树。
    Map map = new HashMap<>(); // 记录中序遍历的值，便于直接获取，而不用每次获取根节点都要遍历一遍。
    private int[] preorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        } 
        return recur(0, 0, inorder.length - 1);
    }
    private TreeNode recur(int pre_root, int in_left, int in_right) {
        if (in_left > in_right) return null;
        
        TreeNode root = new TreeNode(preorder[pre_root]);
        int idx = map.get(preorder[pre_root]);
        root.left = recur(pre_root + 1, in_left, idx - 1);
        root.right = recur(pre_root + (idx - in_left) + 1, idx + 1, in_right);
        return root;
    }
}

时间复杂度：O(n) 遍历所有节点
空间复杂度：O(n) map存放inroder