📃 题目描述

题目链接：

• 剑指 Offer 07. 重建二叉树 (opens new window)
• 105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

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

🔔 解题思路

和上一题的思路一模一样

中序遍历：左根右，前序遍历：根左右

根据前序遍历的最后一个节点，在中序遍历中找到根节点的位置，然后就可以划分左右子树了

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 左闭右开
        return buildTree1(preorder, 0, preorder.length,
                          inorder, 0, inorder.length);
    }

    /**
     * @param preorder (左闭右开)
     * @param preLeft preorder 数组的起始下标
     * @param preRight preorder 数组的终止下标
     * @param inorder (左闭右开)
     * @param inLeft inorder 数组的起始下标
     * @param inRight inorder 数组的终止下标
     * @return
     */
    private TreeNode buildTree1(int[] preorder, int preLeft, int preRight,
                                int[] inorder, int inLeft, int inRight) {
        // 没有元素了
        if (inRight - inLeft < 1) {
            return null;
        }
        // 只有一个元素了
        if (inRight - inLeft == 1) {
            return new TreeNode(inorder[inLeft]);
        }

        // 前序数组的第一个节点为根节点
        TreeNode root = new TreeNode(preorder[preLeft]);
        // 在中序数组中找到根节点的位置
        int index = inLeft;
        for (; index < inRight; index ++) {
            if (inorder[index] == root.val) {
                break;
            }
        }

        // 构建左子树
        root.left = buildTree1(preorder, preLeft + 1, preLeft + 1 + (index - inLeft),
                               inorder, inLeft, index);
        // 构建右子树
        root.right = buildTree1(preorder, preLeft + 1 + (index - inLeft) , preRight,
                                inorder, index + 1, inRight);

        return root;
    }
}

💥 复杂度分析

• 空间复杂度：O(LogN)
• 时间复杂度：O(N)