剑指 Offer 07. 重建二叉树

2022-1-30

题目

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

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

示例 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

解题方法

 /**
     * 递归
     * 时间复杂度：O(n)，其中 n 是树中的节点个数。
     * 空间复杂度：O(n)
     *
     * 对于任意一颗树而言，前序遍历的形式总是
     * [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
     * 即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是
     * [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
     *
     * 只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。
     * 由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，
     * 对上述形式中的所有左右括号进行定位。
     *
     *
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 处理边界条件
        if (preorder == null || inorder == null || preorder.length != inorder.length) return null;
        // 建立HashMap 获取中序遍历节点的信息
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        // 进入递归
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map);
    }

    private TreeNode build(int[] pre, int L1, int R1, int[] in, int L2, int R2, HashMap<Integer, Integer> map) {
        // 如果有空树情况直接返回null
        if (L1 > R1) {
            return null;
        }
        TreeNode head = new TreeNode(pre[L1]);
        if (L1 == R1) {
            return head;
        }
        // 在map中查询根节点在中序遍历中的下标位置
        int find = map.get(pre[L1]);
        // 递归构建左子树
        // find - L2 ： 左子树节点个数
        // L1 + find - L2 ： 左子树中新树前序遍历的右边界
        head.left = build(pre, L1 + 1, L1 + find - L2, in, L2, find - 1, map);
        // 递归构建右子树
        // L1 + find - L2 + 1 ： 右子树中新树前序遍历的左边界
        // find + 1 ：右子树中新树中序遍历的左边界
        head.right = build(pre, L1 + find - L2 + 1, R1, in, find + 1, R2, map);
        return head;
    }