最大二叉树

记牢这一句就够了：对任意一段数组，最大值是根，左边那截递归、右边那截递归。空区间就是空子树(递归出口)。下面从整段开始，逐段找最大值、逐个挂节点。

准备 · 整段数组：先看清输入 [3, 2, 1, 6, 0, 5, 4, 8, 7]。建树从整段开始：扫出全段最大值当根，再向左右两段递归。接下来逐段找最大值、逐个把节点挂上去，看这棵树怎么长出来。

扫描区间 [0,8] · 最大值 8：从整段 [3, 2, 1, 6, 0, 5, 4, 8, 7] 开刀：先扫出整段最大值 8，它就是整棵树的根。最大二叉树的核心就一句话——区间最大值当根。

挂上节点 8 · 划分左右段：节点 8 挂上去了。接着把它两边的数组分别交给递归——左段 [0..6] = [3, 2, 1, 6, 0, 5, 4] → 建左子树；右段 [8..8] = [7] → 建右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。

扫描区间 [0,6] · 最大值 6：轮到子区间 [3, 2, 1, 6, 0, 5, 4]：扫一遍，区间最大值是 6。按规则它当这一段的根，它是父节点 8 的左孩子。

挂上节点 6 · 划分左右段：节点 6 挂上去了。接着把它两边的数组分别交给递归——左段 [0..2] = [3, 2, 1] → 建左子树；右段 [4..6] = [0, 5, 4] → 建右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。

扫描区间 [0,2] · 最大值 3：轮到子区间 [3, 2, 1]：扫一遍，区间最大值是 3。按规则它当这一段的根，它是父节点 6 的左孩子。

挂上节点 3 · 划分左右段：节点 3 挂上去了。接着把它两边的数组分别交给递归——左段为空 → 无左子树；右段 [1..2] = [2, 1] → 建右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。

扫描区间 [1,2] · 最大值 2：轮到子区间 [2, 1]：扫一遍，区间最大值是 2。按规则它当这一段的根，它是父节点 3 的右孩子。

挂上节点 2 · 划分左右段：节点 2 挂上去了。接着把它两边的数组分别交给递归——左段为空 → 无左子树；右段 [2..2] = [1] → 建右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。

扫描区间 [2,2] · 最大值 1：轮到子区间 [1]：扫一遍，区间最大值是 1。按规则它当这一段的根，它是父节点 2 的右孩子。

挂上节点 1 · 划分左右段：节点 1 挂上去了。接着把它两边的数组分别交给递归——左段为空 → 无左子树；右段为空 → 无右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。

扫描区间 [4,6] · 最大值 5：轮到子区间 [0, 5, 4]：扫一遍，区间最大值是 5。按规则它当这一段的根，它是父节点 6 的右孩子。

挂上节点 5 · 划分左右段：节点 5 挂上去了。接着把它两边的数组分别交给递归——左段 [4..4] = [0] → 建左子树；右段 [6..6] = [4] → 建右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。

扫描区间 [4,4] · 最大值 0：轮到子区间 [0]：扫一遍，区间最大值是 0。按规则它当这一段的根，它是父节点 5 的左孩子。

挂上节点 0 · 划分左右段：节点 0 挂上去了。接着把它两边的数组分别交给递归——左段为空 → 无左子树；右段为空 → 无右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。

扫描区间 [6,6] · 最大值 4：轮到子区间 [4]：扫一遍，区间最大值是 4。按规则它当这一段的根，它是父节点 5 的右孩子。

挂上节点 4 · 划分左右段：节点 4 挂上去了。接着把它两边的数组分别交给递归——左段为空 → 无左子树；右段为空 → 无右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。

扫描区间 [8,8] · 最大值 7：轮到子区间 [7]：扫一遍，区间最大值是 7。按规则它当这一段的根，它是父节点 8 的右孩子。

挂上节点 7 · 划分左右段：节点 7 挂上去了。接着把它两边的数组分别交给递归——左段为空 → 无左子树；右段为空 → 无右子树。每一段又重复「找最大值当根」，树就这样一层层长出来。

答案 · 树建完成：所有区间都处理完了，最大二叉树建成：根是整段最大值 8，每个节点都是它所辖那一小段的最大值。这正是"区间最大值当根"自上而下递归的结果。