LeetCode 654. 最大二叉树

2022-04-08 HGNULB 约 12 分钟

文章信息 7 个分类 8 个标签

分类

题目描述

✅ 654. 最大二叉树

题意分析

给一个元素互不相同的整数数组 nums，按如下规则递归地构造一棵树：整个数组的最大值作为根；最大值左边的子数组按同样规则构造成左子树；右边的子数组构造成右子树；空数组对应空节点。返回根节点。

要什么：一棵具体的树，不是某个数值。所以答案的正确性体现在每条父子边上，必须逐条说清楚每个节点的父亲是谁、挂在左边还是右边。

题面的构造规则本身就是一个递归定义，直接照抄成代码就能得到一个可行解。所以真正的问题不是「能不能做」，而是「能做到多快」。规则里那句「区间最大值作为根」是全部代价的来源——朴素做法每次都要线性扫描区间求最大值。

约束透露的信号：数组长度在千级，元素互不相同且非负。互不相同这一条非常关键，它保证了每个区间的最大值唯一，构造出的树也唯一，比较大小时不必纠结相等的情形。数据规模虽然不大（$O(n^2)$ 也能过），但这道题被反复考的原因恰恰在于它有一个漂亮的 $O(n)$ 单调栈解法，面试时被问到就是冲着这个来的。

换个视角看这棵树的结构，能得到一条决定性的观察：对任意元素 nums[i]，它的父亲一定是「它左边第一个比它大的元素」与「它右边第一个比它大的元素」中较小的那一个；若两侧都不存在更大元素，它就是全局最大值即根。这句话把树形结构和「下一个更大元素」这个经典单调栈问题直接挂上了钩。

边界：数组长度至少为 1，所以结果不会是空树；元素互不相同，无需处理相等；数组本身可能是严格递增或严格递减的，此时树退化成一条只有右孩子或只有左孩子的链，递归解法在这种输入下栈深会达到 $n$。

解法：单调递减栈一次构建

核心思路

先看照着题面直译的分治写法：build(lo, hi) 先线性扫描 [lo, hi] 找到最大值下标 m，建节点，然后递归 build(lo, m-1) 与 build(m+1, hi)。每层扫描的总长度是 $O(n)$，树高在随机数据下是 $O(\log n)$，但输入严格递增时树退化成链，层数达到 $n$，总时间变成 $O(n^2)$，递归也有栈溢出风险。瓶颈很清楚：同一段区间的元素被反复扫描比大小，而这些比较结果本可以只算一次。

顺着上面「父亲是两侧第一个更大元素中较小者」的观察往下推，还能得到更细的结论：若父亲取自左边第一个更大元素 L，那么当前节点是 L 的右孩子（它在 L 右边）；若取自右边第一个更大元素 R，那么当前节点是 R 的左孩子。这意味着只要能一次扫描求出每个元素左右两侧第一个更大的元素，树就完全确定了——而这正是单调栈的看家本领。

于是采用从左到右的一次扫描，维护一个从栈底到栈顶严格递减的单调栈，栈中存放的是已经建好的节点。核心不变量是：

任意时刻，栈从底到顶的节点值严格递减；栈中相邻的两个节点已经确定了「上一个是下一个的父亲、下一个挂在上一个的右孩子上」这条边；栈底节点是「已扫描前缀的最大值」，也就是已建部分的根；栈中每个节点的左子树都已经最终确定，而右子树还可能被后续更大的元素改写。

处理新元素 v 时分两步。第一步，把栈顶所有比 v 小的节点弹出——它们比 v 小且在 v 左边，v 会成为包含它们的那个区间的更大值，从而把它们全部收进自己的左子树；由于被弹出的节点从栈底到栈顶递减，最后一个被弹出的（也就是弹出序列中值最大的那个）恰好是这棵左子树的根，所以 cur.left 直接取「最后一次弹出的节点」。第二步，弹完之后若栈非空，栈顶就是 v 左边第一个比它大的元素，此时把 cur 挂成栈顶的右孩子。最后把 cur 压栈，不变量重新成立。

注意第二步会覆盖栈顶之前的右孩子指针，这是正确的而不是 bug：栈顶节点的右子树在扫描过程中会被不断「加高」，旧的右孩子已经在第一步里被 cur 收进左子树，两次赋值语义上是连贯的。

扫描结束后，栈中剩下一条严格递减的链，栈底即全局最大值，就是整棵树的根。用 ArrayDeque 配合 push（等价于 addFirst）时，栈底位于队列的尾部，所以取根要用 peekLast()。

解题步骤

准备一个空的 ArrayDeque<TreeNode> 作为单调栈，从左到右遍历 nums，为每个值新建节点 cur。为什么栈里存节点而不是下标或值：后续要直接改 left / right 指针，存节点省去了下标到节点的二次映射。

准备局部变量 left = null，然后 while (栈非空 && 栈顶值 < v) 不断弹栈并把弹出的节点赋给 left。为什么最后一次弹出的就是左子树的根：栈从底到顶严格递减，被弹出的这一批也满足递减，越晚弹出的越靠近栈底、值越大；这一批元素连同它们各自的子树构成了 v 左侧那段全部小于 v 的区间，区间最大值正是最后弹出的那个。

令 cur.left = left。为什么可以一次性赋值而不需要逐个拼接：被弹出的节点之间的父子关系在它们入栈时就已经通过「挂成栈顶的右孩子」建立好了，弹出时那棵子树已经是完整的，只差认一个父亲。

弹栈结束后若栈非空，执行 栈顶.right = cur。为什么是右孩子：栈顶是 v 左边第一个比它大的元素，v 在它右边，按构造规则必须落在它的右子树里。为什么此处的覆盖是安全的：栈顶原来的右孩子必然小于 v（否则它不会在上一步被弹出，或者它还在栈里且比 v 大就轮不到栈顶做父亲），它已经被收进了 cur.left。

把 cur 压栈。为什么压栈后不变量仍然成立：所有比 v 小的栈顶元素都已被弹走，剩余栈顶必然大于 v，严格递减性得以维持。

遍历结束后返回栈底节点，即 stack.peekLast()。为什么是 peekLast 而不是 peek：ArrayDeque.push 是从头部插入，栈顶在头部、栈底在尾部；栈底是整个数组的最大值，也就是根。这里用 peek() 会拿到最后一个入栈的节点，在严格递减的输入（如 [3,2,1]）下会返回最小的那个元素，结果完全错误。

以 具体用例 nums = [3,2,1,6,0,5] 走一遍。用「栈底 → 栈顶」的顺序描述栈内容。

v = 3：新建节点 3。栈空，不弹栈，left = null，3.left = null。栈空，不设父亲。压栈，栈 = [3]。
v = 2：栈顶 3 不小于 2，不弹栈，2.left = null。栈非空，栈顶 3 是 2 左边第一个更大元素，执行 3.right = 2。压栈，栈 = [3, 2]。
v = 1：栈顶 2 不小于 1，不弹栈，1.left = null。2.right = 1。压栈，栈 = [3, 2, 1]。此时已建好的部分是 3 → 右 2 → 右 1 这条右链，恰好对应前缀 [3,2,1] 的正确答案。
v = 6：栈顶 1 < 6，弹出，left = 1；新栈顶 2 < 6，弹出，left = 2；新栈顶 3 < 6，弹出，left = 3。栈空，弹栈结束。6.left = 3——注意这里挂的是最后弹出的 3，而 3 已经带着 3.right = 2、2.right = 1 这棵完整子树，一次赋值就把整段 [3,2,1] 收编了。栈为空，6 没有父亲。压栈，栈 = [6]。
v = 0：栈顶 6 不小于 0，不弹栈，0.left = null。6.right = 0。压栈，栈 = [6, 0]。
v = 5：栈顶 0 < 5，弹出，left = 0；新栈顶 6 不小于 5，停止。5.left = 0。栈非空，6.right = 5——这一步覆盖了刚才的 6.right = 0，正是「旧的右孩子被新元素收进左子树」的体现，而 0 并没有丢失，它此刻挂在 5.left 上。压栈，栈 = [6, 5]。

遍历结束，栈 = [6, 5]，栈底是 6，返回 6。最终树形：根 6，左子树是 3 →(右) 2 →(右) 1，右子树是 5 →(左) 0。与题面规则逐层核对：[3,2,1,6,0,5] 最大值 6，左段 [3,2,1] 最大值 3、其右段 [2,1] 最大值 2、再右段 [1] 最大值 1；右段 [0,5] 最大值 5、其左段 [0] 最大值 0。完全一致。

代码实现

class Solution {
    // 线性单调栈能用一次扫描保持“候选父子关系”，避免每次在区间里重新找最大值。
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();

        for (int v : nums) {
            TreeNode cur = new TreeNode(v);
            TreeNode left = null;

            while (!stack.isEmpty() && stack.peek().val < v) {
                left = stack.pop();
            }
            cur.left = left;

            if (!stack.isEmpty()) {
                stack.peek().right = cur;
            }
            stack.push(cur);
        }

        // push 从头部入栈，栈底在尾部；栈底即全局最大值，也就是树根。
        return stack.peekLast();
    }
}

func constructMaximumBinaryTree(nums []int) *TreeNode {
    // 线性单调栈能用一次扫描保持“候选父子关系”，避免每次在区间里重新找最大值。
    stack := make([]*TreeNode, 0)
    for _, v := range nums {
        cur := &TreeNode{Val: v}
        var left *TreeNode
        for len(stack) > 0 && stack[len(stack)-1].Val < v {
            left = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }
        cur.Left = left
        if len(stack) > 0 {
            stack[len(stack)-1].Right = cur
        }
        stack = append(stack, cur)
    }
    // 切片头部是栈底，存放的正是全局最大值。
    return stack[0]
}

复杂度分析

时间复杂度：$O(n)$。凭什么：外层每个元素只被处理一次；内层的 while 虽然可能一次弹出多个节点，但每个节点在整个过程中最多入栈一次、出栈一次，弹栈总次数不超过 $n$，两层循环合起来是均摊 $O(n)$ 而非 $O(n^2)$。相比之下，直译题面的分治解法在严格递增输入下会退化到 $O(n^2)$。

空间复杂度：$O(n)$。凭什么：单调栈在严格递减的输入（如 [5,4,3,2,1]）下会同时容纳全部 $n$ 个节点；此外要为 $n$ 个节点分配对象，这部分是输出本身的必需开销。好处是全程没有递归，不存在栈溢出风险。

关键点总结

把「构造规则」翻译成「每个元素的父亲是谁」，是从分治跳到线性的关键一步。原规则是自顶向下的，难以线性化；改写成「父亲 = 左右两侧第一个更大元素中较小的那个」之后，问题立刻变成两个经典的单调栈子问题。

单调栈的本质是维护「尚未被更大元素终结的候选集合」。栈中元素严格递减，等价于说它们各自的右子树还开放、还可能接纳新节点；一个元素被弹出，就意味着它的右子树封版、同时它整体沉入某个更大元素的左子树。

一次赋值收编整棵子树，靠的是弹出顺序的单调性。因为被弹出的一批元素之间的父子边早已建好，只需把最后弹出的那个（值最大的）认作子树根即可，无需在循环里做任何拼接。

「覆盖旧指针」在增量构造类的单调栈里是常态而非错误，前提是被覆盖的那个旧值已经在同一轮中被安置到了别处。写这类代码时要能说清「旧的右孩子去哪了」，说不清就说明逻辑有洞。

容器 API 的方向必须和心智模型对齐。ArrayDeque.push 从头部入栈，因此栈顶用 peek()、栈底用 peekLast()；用 Go 切片模拟时则相反，栈顶是 stack[len-1]、栈底是 stack[0]。取根时方向搞反，在严格递减的输入下会静默返回最小元素。

面试视角：面试官问这题，$O(n^2)$ 的分治只能算及格。标准答法是先用一分钟说清分治解法和它在递增输入下退化到 $O(n^2)$ 的原因，然后给出「父亲是两侧第一个更大元素中较小者」的观察，再写单调栈。写完后主动补一句「这棵树其实就是笛卡尔树，同一套单调栈还能解 84. 柱状图中最大的矩形」，能明显拉开区分度。

易错点总结

错误写法：最后返回 stack.peek()（拿栈顶当根） → 用例 nums = [3,2,1]，全程无弹栈，栈从底到顶是 3, 2, 1，peek() 返回节点 1，得到的「树」只有一个孤立节点 1，而正确的根是 3。

错误写法：最后写成 while (!stack.isEmpty()) root = stack.removeLast(); 再返回 root → 用例 nums = [3,2,1]，循环依次移除尾部的 3、2，最后一次移除的是头部的 1，root 停在 1 上，同样返回错误的根。想取栈底就该只取一次尾部元素，反复弹到空反而拿到了栈顶。

错误写法：弹栈条件写成 stack.peek().val <= v → 本题元素互不相同，用例上看不出差别，但把这个习惯带到允许重复值的变形题时，相等元素会被错误弹出，导致同一个值被重复收编、父子关系错乱。弹栈条件的严格与否必须与题目对相等的定义一致。

错误写法：在弹栈的 while 里写 cur.left = stack.pop()（每次都覆盖） → 用例 nums = [3,2,1,6]，弹出顺序是 1、2、3，最终 6.left 停在 3 上，结果碰巧正确；但若写成 if (cur.left == null) cur.left = stack.pop();，6.left 会停在第一个弹出的 1 上，节点 3 和 2 整段丢失。必须取最后一次弹出的节点。

错误写法：先执行 stack.peek().right = cur 再做弹栈 → 用例 nums = [3,2,1,6]，处理 6 时会先把 6 挂到栈顶 1 的右边，然后又把 1 弹出收进 6.left，于是 1.right 指回 6、6.left 指向 1，形成父子互指的环，遍历时死循环。顺序必须是先弹栈、再认父亲。

错误写法：弹栈后忘记 cur.left = left，只在栈非空时挂右孩子 → 用例 nums = [3,2,1,6,0,5]，节点 6 的左子树 [3,2,1] 整段丢失，最终树只剩 6 →(右) 5 →(左) 0，节点数从 6 个变成 3 个。

错误写法：Go 中返回 stack[len(stack)-1] → 用例 nums = [3,2,1]，切片是 [3,2,1]，返回末尾的节点 1；Go 切片模拟栈时头部才是栈底，取根要用 stack[0]。

错误写法：直译题面写成递归分治，每层用 for 扫描区间求最大值 → 用例 nums = [1,2,3,...,1000] 严格递增时，树退化成一条长 1000 的右链，每层扫描长度依次是 1000、999、…，总比较次数约 $5 \times 10^5$，本题数据下能过，但递归深度也达到 1000；同样的写法搬到 $n = 10^5$ 的变形题上会同时超时和栈溢出。

错误写法：以为「栈顶的右孩子被覆盖」是 bug，于是加上 if (stack.peek().right == null) 的保护 → 用例 nums = [6,0,5]，处理 5 时 6.right 已是 0，保护条件不成立于是不挂，节点 5 及其左子树 0 全部游离在树外，返回的树只有 6 和 0 两个节点。

相似题目

题目	难度	考察点
84. 柱状图中最大的矩形	困难	同样用单调栈求两侧第一个更小元素，但要在弹栈的瞬间结算面积而不是连边
739. 每日温度	中等	单调栈的最小形态，只求右侧第一个更大元素的距离，栈里存下标而非节点
496. 下一个更大元素 I	简单	在单调栈之外多一层哈希映射，把子数组的查询转接到主数组的预处理结果上
503. 下一个更大元素 II	中等	数组首尾相接，靠遍历两遍下标取模来模拟环形，考的是边界的处理方式
42. 接雨水	困难	单调递减栈按横向层结算积水，弹栈时需要同时用到左右两个边界而非单侧
316. 去除重复字母	中等	单调栈维护字典序，弹栈条件里额外附加「后面还有没有这个字符」的可行性判断
105. 从前序与中序遍历序列构造二叉树	中等	同为递归建树，但根由前序给出、左右划分靠中序定位，可用哈希把定位降到 $O(1)$
108. 将有序数组转换为二叉搜索树	简单	划分点由「取中点」直接给定而非依赖数据，因此天然平衡，不存在退化成链的风险