最大二叉树 图解题解

这道题到底在问什么

输入

nums = [3,2,1,6,0,5,4,8,7]

输出

见动画逐步建出的树

最优解：一步一步想明白

1. 3记牢这一句就够了：对任意一段数组，最大值是根，左边那截递归、右边那截递归。空区间就是空子树(递归出口)。下面从整段开始，逐段找最大值、逐个挂节点。
2. 4nums = [3, 2, 1, 6, 0, 5, 4, 8, 7]先看清输入 [3, 2, 1, 6, 0, 5, 4, 8, 7]。建树从整段开始：扫出全段最大值当根，再向左右两段递归。接下来逐段找最大值、逐个把节点挂上去，看这棵树怎么长出来。
3. 5max(nums[0..8]) = 8从整段 [3, 2, 1, 6, 0, 5, 4, 8, 7] 开刀：先扫出整段最大值 8，它就是整棵树的根。最大二叉树的核心就一句话——区间最大值当根。
4. 6root=8; 左[0,6] 右[8,8]节点 8 挂上去了。接着把它两边的数组分别交给递归——左段 [0..6] = [3, 2, 1, 6, 0, 5, 4] → 建左子树；右段 [8..8] = [7] → 建右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。
5. 7max(nums[0..6]) = 6轮到子区间 [3, 2, 1, 6, 0, 5, 4]：扫一遍，区间最大值是 6。按规则它当这一段的根，它是父节点 8 的左孩子。
6. 8root=6; 左[0,2] 右[4,6]节点 6 挂上去了。接着把它两边的数组分别交给递归——左段 [0..2] = [3, 2, 1] → 建左子树；右段 [4..6] = [0, 5, 4] → 建右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。
7. 9max(nums[0..2]) = 3轮到子区间 [3, 2, 1]：扫一遍，区间最大值是 3。按规则它当这一段的根，它是父节点 6 的左孩子。
8. 10root=3; 左[0,-1] 右[1,2]节点 3 挂上去了。接着把它两边的数组分别交给递归——左段为空 → 无左子树；右段 [1..2] = [2, 1] → 建右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。
9. 11max(nums[1..2]) = 2轮到子区间 [2, 1]：扫一遍，区间最大值是 2。按规则它当这一段的根，它是父节点 3 的右孩子。
10. 12root=2; 左[1,0] 右[2,2]节点 2 挂上去了。接着把它两边的数组分别交给递归——左段为空 → 无左子树；右段 [2..2] = [1] → 建右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。
11. 13max(nums[2..2]) = 1轮到子区间 [1]：扫一遍，区间最大值是 1。按规则它当这一段的根，它是父节点 2 的右孩子。
12. 14root=1; 左[2,1] 右[3,2]节点 1 挂上去了。接着把它两边的数组分别交给递归——左段为空 → 无左子树；右段为空 → 无右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。
13. 15max(nums[4..6]) = 5轮到子区间 [0, 5, 4]：扫一遍，区间最大值是 5。按规则它当这一段的根，它是父节点 6 的右孩子。
14. 16root=5; 左[4,4] 右[6,6]节点 5 挂上去了。接着把它两边的数组分别交给递归——左段 [4..4] = [0] → 建左子树；右段 [6..6] = [4] → 建右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。
15. 17max(nums[4..4]) = 0轮到子区间 [0]：扫一遍，区间最大值是 0。按规则它当这一段的根，它是父节点 5 的左孩子。
16. 18root=0; 左[4,3] 右[5,4]节点 0 挂上去了。接着把它两边的数组分别交给递归——左段为空 → 无左子树；右段为空 → 无右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。
17. 19max(nums[6..6]) = 4轮到子区间 [4]：扫一遍，区间最大值是 4。按规则它当这一段的根，它是父节点 5 的右孩子。
18. 20root=4; 左[6,5] 右[7,6]节点 4 挂上去了。接着把它两边的数组分别交给递归——左段为空 → 无左子树；右段为空 → 无右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。
19. 21max(nums[8..8]) = 7轮到子区间 [7]：扫一遍，区间最大值是 7。按规则它当这一段的根，它是父节点 8 的右孩子。
20. 22root=7; 左[8,7] 右[9,8]节点 7 挂上去了。接着把它两边的数组分别交给递归——左段为空 → 无左子树；右段为空 → 无右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。
21. 23root = 8所有区间都处理完了，最大二叉树建成：根是整段最大值 8，每个节点都是它所辖那一小段的最大值。这正是"区间最大值当根"自上而下递归的结果。

⚠️ 容易写错的地方

完整代码（Java / Python / C++）

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }
    private TreeNode build(int[] nums, int lo, int hi) {
        if (lo > hi) return null;              // 空区间 → 空子树
        int mi = lo;                            // 找区间最大值的下标
        for (int i = lo + 1; i <= hi; i++)
            if (nums[i] > nums[mi]) mi = i;
        TreeNode root = new TreeNode(nums[mi]); // 区间最大值当根
        root.left  = build(nums, lo, mi - 1);   // 左段建左子树
        root.right = build(nums, mi + 1, hi);   // 右段建右子树
        return root;
    }
}

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        def build(lo: int, hi: int) -> TreeNode:
            if lo > hi:                         # 空区间 → 空子树
                return None
            mi = lo                              # 找区间最大值的下标
            for i in range(lo + 1, hi + 1):
                if nums[i] > nums[mi]:
                    mi = i
            root = TreeNode(nums[mi])            # 区间最大值当根
            root.left  = build(lo, mi - 1)       # 左段建左子树
            root.right = build(mi + 1, hi)       # 右段建右子树
            return root
        return build(0, len(nums) - 1)

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return build(nums, 0, (int)nums.size() - 1);
    }
private:
    TreeNode* build(vector<int>& nums, int lo, int hi) {
        if (lo > hi) return nullptr;            // 空区间 → 空子树
        int mi = lo;                             // 找区间最大值的下标
        for (int i = lo + 1; i <= hi; i++)
            if (nums[i] > nums[mi]) mi = i;
        TreeNode* root = new TreeNode(nums[mi]); // 区间最大值当根
        root->left  = build(nums, lo, mi - 1);   // 左段建左子树
        root->right = build(nums, mi + 1, hi);   // 右段建右子树
        return root;
    }
};

复杂度

面试官可能追问