LeetCode 333. 最大二叉搜索子树

2021-08-14 HGNULB 约 5 分钟

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

分类

LeetCode CodeTop 中等未解决会员题 2-5 网易

题目描述

✅ 333. 最大二叉搜索子树

题意分析

在给定二叉树中，找出节点数最多的二叉搜索子树，返回其节点数。子树必须包含所选根节点的全部后代，不能删掉其中不满足条件的节点；二叉搜索树要求左侧所有值严格小于根、右侧所有值严格大于根。

解法：后序遍历 + 子树信息合并

核心思路

[!blue]

是否能把当前节点和左右孩子合并，取决于两棵完整子树是否都是 BST，以及它们的值域。因此使用后序遍历，先从左右孩子取得 isBst、size、min、max 四项信息，再判断当前子树。

isBst 表示当前整棵子树是否合法，size 始终保存其内部最大 BST 的节点数。当前子树合法时，它本身就是最大的 BST，size 也就是整棵子树的大小，此时 min、max 保存真实最小值和最大值；不合法时，极值不参与后续合并。

若左右都合法，且 左侧最大值 < 当前值 < 右侧最小值，就能保证所有后代同时满足 BST 条件。新规模为 left.size + right.size + 1，最小值来自左子树或当前节点，最大值来自右子树或当前节点。只比较直接孩子不足以保证更深后代的范围，所以需要向上汇总极值。

若任一条件失败，包含当前根的完整子树就不合法。其他可能的 BST 子树只能完整地位于左边或右边，因此保留 max(left.size, right.size)，并将 isBst 设为 false。这样父节点既知道不能继续合并，又不会丢掉这棵子树内部已有的最佳答案。

空树视为合法，规模为 0。Java 将空树最小值设为 Long.MAX_VALUE、最大值设为 Long.MIN_VALUE，使空孩子不会限制 int 节点；Go 则在孩子规模为 0 时跳过极值比较，避免整数极值与空树哨兵相等。根返回的 size 就是全树答案，空树自然返回 0。

解题步骤

空节点返回“合法、规模 0、空树极值”的信息。

递归取得左右子树信息，检查它们都合法且极值满足严格大小关系。

可以合并时，返回整棵当前子树的规模和极值；否则返回非法标记和两侧最大规模。

返回根节点汇总信息中的 size。

代码实现

class Solution {
    public int largestBSTSubtree(TreeNode root) {
        return dfs(root).size;
    }

    private Info dfs(TreeNode node) {
        if (node == null) {
            return new Info(true, 0, Long.MAX_VALUE, Long.MIN_VALUE);
        }

        // 后序取得整棵子树信息，非法子树的极值不参与合并
        Info left = dfs(node.left);
        Info right = dfs(node.right);

        if (left.isBst && right.isBst && node.val > left.max && node.val < right.min) {
            long min = Math.min(left.min, node.val);
            long max = Math.max(right.max, node.val);

            return new Info(true, left.size + right.size + 1, min, max);
        }

        // 当前整棵子树非法，仍保留内部最大的合法子树规模
        int best = Math.max(left.size, right.size);

        return new Info(false, best, 0, 0);
    }

    private static class Info {
        boolean isBst;
        int size;
        long min;
        long max;

        Info(boolean isBst, int size, long min, long max) {
            this.isBst = isBst;
            this.size = size;
            this.min = min;
            this.max = max;
        }
    }
}

func largestBSTSubtree(root *TreeNode) int {
    return dfsLargest(root).size
}

type bstInfo struct {
    isBst bool
    size  int
    min   int
    max   int
}

func dfsLargest(node *TreeNode) bstInfo {
    if node == nil {
        return bstInfo{isBst: true, size: 0, min: maxInt(), max: minInt()}
    }

    // 后序取得整棵子树信息，非法子树的极值不参与合并
    left := dfsLargest(node.Left)
    right := dfsLargest(node.Right)

    // 空孩子不施加极值约束，避免与真实整数边界碰撞
    if left.isBst && right.isBst &&
        (left.size == 0 || node.Val > left.max) &&
        (right.size == 0 || node.Val < right.min) {
        minVal := left.min
        if node.Val < minVal {
            minVal = node.Val
        }

        maxVal := right.max
        if node.Val > maxVal {
            maxVal = node.Val
        }

        return bstInfo{isBst: true, size: left.size + right.size + 1, min: minVal, max: maxVal}
    }

    // 当前整棵子树非法，仍保留内部最大的合法子树规模
    best := left.size
    if right.size > best {
        best = right.size
    }

    return bstInfo{isBst: false, size: best, min: 0, max: 0}
}

func maxInt() int {
    return int(^uint(0) >> 1)
}

func minInt() int {
    return -maxInt() - 1
}

复杂度分析

时间复杂度：$O(n)$，n 为节点数，每个节点只访问一次，合并四项信息为常数时间。

空间复杂度：$O(h)$，h 为树高，来自递归栈与各活动层保留的信息；退化链时为 $O(n)$。

关键点总结

[!green]

合法时规模是整棵当前子树，非法时是内部最优，必须按标记理解。

只有非空合法孩子的极值才约束当前节点。

易错点总结

[!yellow]

只比较直接孩子，可能漏掉更深后代违反范围。

非法就把规模清零，会丢掉子树内部答案。

合并规模取最大加一，漏算另一侧节点。

相似题目

题目	难度	关联与区别
98. 验证二叉搜索树	中等	验证BST的上下界条件相同，本题还要向父节点返回子树有效性、最小值、最大值及大小。
1373. 二叉搜索子树的最大键值和	困难	同样后序判断BST子树，原题最大化节点和，本题最大化节点数量。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2021/60702983

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！