LeetCode 654. 最大二叉树

约 4 分钟
文章信息 7 个分类 6 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 华为 美团
标签
数组 树 二叉树 栈 分治 单调栈

题目描述

✅ 654. 最大二叉树

image-20260928224434735

image-20260928224434736

image-20260928224434737

题意分析

每个区间的最大值作为根，最大值左边的数组部分构成左子树，右边构成右子树。元素互不相同，因此树形唯一。直接递归时会反复寻找区间最大值，可以利用单调栈从左到右一次构建。

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

核心思路

[!blue]

最大二叉树的父节点大于子树中的所有值，中序遍历则保持原数组顺序。把新值追加到数组末尾时，它在中序遍历中也应位于最后，只需调整当前树从根沿右孩子走出的链。用栈保存这条右侧链，栈底到栈顶的值严格递减。

为新值创建节点 cur，连续弹出比它小的栈顶。这些节点都在新值左边，且值更小，应成为 cur 的左子树。最后弹出的节点是这一段右侧链上最高的祖先，原有指针仍连接着整段子树，所以只需令 cur.left 指向最后弹出的节点，就能保留全部旧节点。

若弹栈后还有节点，剩余栈顶的值大于 cur，令它的右孩子改为 cur。被替换的旧右子树已经接到 cur.left，不会丢失；若没有弹出过节点，旧栈顶原本就是右侧链末端，直接接上新右孩子即可。若栈被弹空，说明新值超过整个前缀，cur 就成为新根。

最后把 cur 入栈，新的右侧链仍然递减，树的中序顺序也仍是已经读入的数组前缀。父子大小关系和原数组顺序同时保持，因此构建结果符合最大二叉树的递归定义。全部处理后，栈底就是全局最大值所在的根节点。

解题步骤

  1. 创建空栈，按数组顺序为每个值创建 cur，令临时左子树指针为空。
  2. 连续弹出更小栈顶，每次用弹出的节点覆盖临时指针，保留最后弹出者。
  3. 将该指针接为 cur 的左孩子；栈仍非空时，将剩余栈顶的右孩子接为 cur。
  4. 将 cur 入栈，继续处理下一个值。
  5. 返回栈底。Java 的 push 从双端队列头部入栈，栈底用 peekLast() 读取；Go 切片从尾部入栈，栈底就是下标 $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)$，每个节点至多入栈、出栈各一次。
  • 空间复杂度：$O(n)$，递减输入时栈保存全部节点，输出节点另计。

关键点总结

[!green]

  • 栈代表当前前缀树的右侧链，其中部分父子关系还可能被新节点改写。
  • 左子树取最后弹出者，而不是最先弹出者。

易错点总结

[!yellow]

  • 只保留第一个弹出节点，会丢掉这一段的其他祖先。
  • 先挂右孩子再弹栈，可能形成反向指针环。
  • 返回栈顶，会把最后待定节点误当成整棵树根。

相似题目

题目 难度 关联与区别
998. 最大二叉树 II 中等 原题在已有最大二叉树对应数组末尾加一个值，可利用本题结构只调整右侧路径。
105. 从前序与中序遍历序列构造二叉树 中等 同样由输入序列确定根并递归分左右区间，本题根是区间最大值，原题根来自前序位置。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/leetcode-654
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！