最大二叉树 II

记住这句口诀:追加在末尾,只走右链;比 val 小就让位、比 val 大就继续往右。后面每帧都在套它。

最大树 · 认识它：这是一棵最大树。它的规矩是:每个节点都比自己子树里的所有节点大。所以最大的 80 坐在根上。

最大树 · 性质：验证一下:80 比它子树里的 30、60、20 全都大,所以它才有资格当根。这就是最大树最核心的那条规矩。

最大树 · 递归性质：这条规矩一层层往下都成立:右边的 60 也比它子树里的 20 大。每一棵子树都自带同一条规矩。

回看 · 原数组：这棵树是从数组 a = 30, 80, 20, 60 用 Construct 建出来的:每次取区间最大值当根,左边的数建左子树,右边的数建右子树。先把数组的样子记牢。

追加 · 新值 70：现在来了新值 70,题目要求把它追加到数组 a 的最末尾,得到 b = 30, 80, 20, 60, 70。我们要的是 b 重新建成的最大树。

关键 · 只走右链：关键一步想通就赢了:70 排在数组最末尾,在 Construct 里它永远排在所有现存元素后面,所以只可能挂在某个节点的右边。我们只需沿着根的右链往下找,右链就是 80 到 60 这一串。

关键 · 左边不碰：左子树 30 这一边完全不用碰。因为 70 在末尾,绝不会跑到现存元素的左边去,注意力全部放在右链上。

右链下行 · 看 80：从根 80 开始下行。拿 70 和 80 比一比:70 能不能比 80 还大、从而取代它当新根?

右链下行 · 判 80：70 比 80 小,所以 80 稳坐根位不动。70 只能沉进 80 的右子树继续找位置,指针准备滑向它的右孩子。

右链下行 · 移动：指针顺着 80 的右指针滑到下一个节点 60,继续往右链深处找它的位置。

右链下行 · 看 60：现在指针来到右孩子 60。再比一次:70 和 60 谁大?

右链下行 · 命中：70 比 60 大,插入点就定在这儿!按最大树的规矩,70 要当这一段的新根,原来的 60 得给它让位。

插入 · 让位：要注意:让位的是 60 连着它下面的 20 这一整棵子树,谁都不能丢。下一步把这整棵挂到新节点 70 的左边。

插入 · 新建 70：新建一个节点 70,放到 60 原来的位置上,也就是接在 80 的右边。

插入 · 挂左孩子：刚才让位的 60 加上 20 这一整棵,挂到 70 的左孩子上。因为它们都比 70 小,正好待在 70 的左子树里,规矩一点没破。

插入 · 右为空：70 的右孩子是空的。道理也简单:70 是数组最后一个元素,它后面再没有别的数,右边自然空着。

插入 · 接回 80：最后把 80 原来指向 60 的那根右指针,改成指向 70。这样新节点 70 就正式接回了整棵树。

插入 · 成形：新的最大树成形了。80 还是根,左边的 30 没动,右边由 60 换成了 70,70 底下挂着 60 和 20。

验证 · 父子：验证一下规矩有没有破。先看父子:80 > 70,根依然是最大,这一关过了。

验证 · 子树：再看 70 这棵子树:70 > 60 > 20,每个节点都比自己子树里的大,完全满足最大树的规矩。

回放 · 全程：回放整个过程:从根 80 沿右链下行,70 一路比下来,到 60 时终于更大,就在那里取代 60、把 60 子树收作左孩子。一次右链下行,插入完成。

回放 · 高效：整趟只碰了右链上的 80 和 60 两个节点,没有重建任何子树,这就是增量插入的高效之处。

边界先想清:val 最大时在根处就让位;val 最小时一路走到右链末端;单节点时直接比一次。

面试重点:讲清「末尾追加 → 只在右侧 → 沿右链」这条推理链,以及和最大二叉树 I 的增量关系。