Version: Next

333.最大BST子树

333. 最大 BST 子树

难度 中等

给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，并返回该子树的大小。其中，最大指的是子树节点数最多的。

二叉搜索树（BST）中的所有节点都具备以下属性：

  • 左子树的值小于其父（根）节点的值。
  • 右子树的值大于其父（根）节点的值。

注意:

  • 子树必须包含其所有后代。

进阶:

  • 你能想出 O(n) 时间复杂度的解法吗？

Given the root of a binary tree, find the largest subtree, which is also a Binary Search Tree (BST), where the largest means subtree has the largest number of nodes.

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties:

The left subtree values are less than the value of their parent (root) node's value. The right subtree values are greater than the value of their parent (root) node's value. Note: A subtree must include all of its descendants.

Follow up: Can you figure out ways to solve it with O(n) time complexity?

示例 1：

img

输入：root = [10,5,15,1,8,null,7]
输出：3
解释：本例中最大的 BST 子树是高亮显示的子树。返回值是子树的大小，即 3 。

示例 2：

输入：root = [4,2,7,2,3,5,null,2,null,null,null,null,null,1]
输出：2

提示：

  • 树上节点数目的范围是 [0, 104]
  • -104 <= Node.val <= 104

自顶向下——前序遍历

  • 定义方法 func()，返回以 root 为根节点的二叉树的最大BST子树的节点数量
  • 如果以 root 为根节点的二叉树 S 就是一颗 BST（需要执行判断方法），那么返回 S 的节点数量（需要执行计数方法）
  • 否则：递归，返回 func(root.left) 和 func(root.rignt) 中的最大值
  • 时间复杂度：
    • 前序遍历：O(n)
    • 判断是否为 BST + 计数：O(2n)
    • O(n ^ 2)

自底向上——后序遍历

先判断下方的子树是不是BST，如果不是，则它上侧的都不是BST

  • 获取左子树的最大 BST 信息

  • 获取右子树的最大 BST 信息

  • 一下四种情况说明 root 节点就是以 root 为根节点的二叉树的最大BST子树的根节点

  • 如果左子树中的最大BST子树就是左子树本身
    且 右子树中没有最大BST子树
    且 root 大于左子树中的最大值
    则 root 加入左子树会形成更大的BST
    故返回 root
    同理 如果右子树中的最大BST就是右子树本身
    .... 返回 root
  • 如果左子树中的最大BST子树就是左子树本身
    如果右子树中的最大BST子树就是右子树本身
    且 根节点大于左BST子树中的最大值
    且 根节点小于右BST子树中的最小值
    则根节点的加入构成一个更大的BST，即整个二叉树本身就是最大BST，那么返回 root
  • 如果左右子树都没有最大BST子树，则只考虑一个单节点 root，此时它自己构成一个BST
    返回 root

  • 以 root 为根节点，构建BST子树信息

  • 如果以上都不满足，说明最大BST子树不是以 root 为根节点的

    • 选左侧最大BST和右侧最大BST中 size 较大的那个
    • 如果仅左侧 或 仅右侧存在最大BST，就选存在的那个

定义内部类 Info

  • 用来记录 BST 的信息：
    • BST 根节点 root
    • BST 节点数目 size
    • BST 当中的最大值
    • BST 当中的最小值
// BST 信息
private static class Info {
// 根节点
public TreeNode root;
// 节点数目
public int size;
// 最大值
public int max;
// 最小值
public int min;
public Info() {
}
public Info(TreeNode root, int size, int max, int min) {
this.root = root;
this.size = size;
this.max = max;
this.min = min;
}
}

定义 getInfo(TreeNode root) 方法

  • 作用：返回以 root 为根节点的二叉树的 BST 子树信息
  • 实现：

    • 计算 li = getInfo(root.left)，ri = getInfo(root.right)

    • 如果几下条件成立，说明以 root 为根节点的二叉树就是最大 BST 子树

      • li == null || (li.root = root.left && li.max < root.val)
        ri == null || (ri.root = root.right && li,min > root.val)

    • 如果 li != null && ri != null

      • 如果 li.size > ri.size，返回 li，否则返回 ri

    • 如果 li != null，返回 li，否则返回 ri

public int largestBSTSubtree(TreeNode root) {
return (root == null) ? 0 : getInfo(root).size;
}
// 返回以 root 为根节点的二叉树的最大BST子树信息
private Info getInfo(TreeNode root) {
if (root == null) return null;
// 获取左右子树的最大 BST 信息
Info leftInfo = getInfo(root.left);
Info rightInfo = getInfo(root.right);
// 如果左子树中的最大BST子树就是左子树本身
// 且 右子树中没有最大BST子树
// 且 root 大于左子树中的最大值
// 则 root 加入左子树会形成更大的BST
// 故返回 root
/*if (leftInfo != null && rightInfo == null
&& leftInfo.root == root.left && root.val > leftInfo.max)*/
// 同理 如果右子树中的最大BST就是右子树本身
// .... 返回 root
/*if (leftInfo == null && rightInfo != null
&& rightInfo.root == root.right && root.val < rightInfo.min)*/
// 如果左子树中的最大BST子树就是左子树本身
// 如果右子树中的最大BST子树就是右子树本身
// 且 根节点大于左BST子树中的最大值
// 且 根节点小于右BST子树中的最小值
// 则根节点的加入构成一个更大的BST，即整个二叉树本身就是最大BST，那么返回 root
/*if (leftInfo != null && rightInfo != null
&& leftInfo.root == root.left && root.val > leftInfo.max
&& rightInfo.root == root.right && root.val < rightInfo.min)*/
// 如果左右子树都没有最大BST子树，则只考虑一个单节点 root，此时它自己构成一个BST
// 返回 root
// if (leftInfo == null && rightInfo == null)
int leftBstSize = -1, rightBstSize = -1, max = root.val, min = root.val;
if (leftInfo == null) {
leftBstSize = 0;
} else if (leftInfo.root == root.left && root.val > leftInfo.max) {
leftBstSize = leftInfo.size;
min = leftInfo.min;
}
if (rightInfo == null) {
rightBstSize = 0;
} else if (rightInfo.root == root.right && root.val < rightInfo.min) {
rightBstSize = rightInfo.size;
max = rightInfo.max;
}
// bst 就是以二叉树的 root 节点为根节点
if (leftBstSize >= 0 && rightBstSize >= 0)
return new Info(root, leftBstSize + rightBstSize + 1, max, min);
// 来到这里说明 root 不是最大BST子树的根节点
// 如果左右都存在合法的最大BST子树，且根节点的加入不会再形成一个更大的BST
// 那么选子树中较大的那个
if (leftInfo != null && rightInfo != null)
return leftInfo.size > rightInfo.size ? leftInfo : rightInfo;
// 这里：说明 leftInfo rightInfo 中只有一个不为 null
return leftInfo != null ? leftInfo : rightInfo;
}
// BST 信息
private static class Info {
// 根节点
public TreeNode root;
// 节点数目
public int size;
// 最大值
public int max;
// 最小值
public int min;
public Info() {
}
public Info(TreeNode root, int size, int max, int min) {
this.root = root;
this.size = size;
this.max = max;
this.min = min;
}
}