105. 从前序与中序遍历序列构造二叉树

力扣题目链接 (opens new window)

题目描述

给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。树中节点值互不相同。

示例 1：

输入：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出：[3,9,20,null,null,15,7]

示例 2：

输入：preorder = [-1], inorder = [-1]
输出：[-1]

思路

前序数组的第一个元素是谁？根节点。知道根节点后，如何区分左右子树？去中序数组中找这个值：左边全是左子树，右边全是右子树。这和代码随想录构造二叉树里 106 题的切分思路相同，只是根节点在前序数组开头，而不是后序数组结尾。

递归函数传入前序、中序各自的左闭右开区间。前序区间为空就返回空节点。假设中序左区间长度为 leftSize，则前序数组跳过根节点后的 leftSize 个元素属于左子树，剩余元素属于右子树。区间边界统一用左闭右开，录友写到这里最好拿示例手算一轮。

模拟过程

主站的 105 题配图可以直接看出前中序切分后的树形：

前序 [3,9,20,15,7] 首元素 3 是根；中序 [9,3,15,20,7] 以 3 切开，左边 [9] 长度为 1，右边 [15,20,7]。因此前序接下来的一个元素 9 属于左子树，其余 [20,15,7] 属于右子树，再按同样规则递归。

解题代码

class Solution {
    unordered_map<int, int> index;
    TreeNode* build(const vector<int>& preorder, int preBegin, int preEnd,
                    int inBegin, int inEnd) {
        if (preBegin == preEnd) return nullptr;
        int rootValue = preorder[preBegin];
        int split = index[rootValue];
        int leftSize = split - inBegin;
        TreeNode* root = new TreeNode(rootValue);
        // 前序跳过根节点，再按中序左区间长度切分
        root->left = build(preorder, preBegin + 1, preBegin + 1 + leftSize,
                           inBegin, split);
        root->right = build(preorder, preBegin + 1 + leftSize, preEnd,
                            split + 1, inEnd);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        index.clear();
        for (int i = 0; i < inorder.size(); ++i) index[inorder[i]] = i;
        return build(preorder, 0, preorder.size(), 0, inorder.size());
    }
};

复杂度分析

• 时间复杂度：O(n)，哈希表查找中序切分位置，每个节点构造一次。
• 空间复杂度：O(n)，哈希表和递归栈，最坏树高为 n。

其他语言

Python3

class Solution:
    def buildTree(self, preorder, inorder):
        index = {value: i for i, value in enumerate(inorder)}
        def build(pre_begin, pre_end, in_begin, in_end):
            if pre_begin == pre_end:
                return None
            value = preorder[pre_begin]
            split = index[value]
            left_size = split - in_begin
            root = TreeNode(value)
            root.left = build(pre_begin + 1, pre_begin + 1 + left_size, in_begin, split)
            root.right = build(pre_begin + 1 + left_size, pre_end, split + 1, in_end)
            return root
        return build(0, len(preorder), 0, len(inorder))

Java

class Solution {
    Map<Integer, Integer> index = new HashMap<>();
    int[] preorder;
    TreeNode build(int pb, int pe, int ib, int ie) {
        if (pb == pe) return null;
        int value = preorder[pb], split = index.get(value);
        int leftSize = split - ib;
        TreeNode root = new TreeNode(value);
        root.left = build(pb + 1, pb + 1 + leftSize, ib, split);
        root.right = build(pb + 1 + leftSize, pe, split + 1, ie);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        index.clear();
        for (int i = 0; i < inorder.length; i++) index.put(inorder[i], i);
        return build(0, preorder.length, 0, inorder.length);
    }
}

Go

func buildTree(preorder []int, inorder []int) *TreeNode {
    index := map[int]int{}
    for i, value := range inorder { index[value] = i }
    var build func(int, int, int, int) *TreeNode
    build = func(pb, pe, ib, ie int) *TreeNode {
        if pb == pe { return nil }
        value := preorder[pb]
        split := index[value]
        leftSize := split - ib
        root := &TreeNode{Val: value}
        root.Left = build(pb+1, pb+1+leftSize, ib, split)
        root.Right = build(pb+1+leftSize, pe, split+1, ie)
        return root
    }
    return build(0, len(preorder), 0, len(inorder))
}

JS

var buildTree = function(preorder, inorder) {
    const index = new Map(inorder.map((value, i) => [value, i]));
    function build(pb, pe, ib, ie) {
        if (pb === pe) return null;
        const value = preorder[pb], split = index.get(value);
        const leftSize = split - ib;
        const root = new TreeNode(value);
        root.left = build(pb + 1, pb + 1 + leftSize, ib, split);
        root.right = build(pb + 1 + leftSize, pe, split + 1, ie);
        return root;
    }
    return build(0, preorder.length, 0, inorder.length);
};

与代码随想录联系

105 的讲解与代码收在主站106.从中序与后序遍历序列构造二叉树的“相关题目推荐”部分。两题都要先确定根，再用中序数组划分左右子树；区别是根分别来自前序开头和后序结尾。