func largestBSTSubtree(root *TreeNode) int {
ret, _, _, _ := ls(root)
return ret
}
// bool表示子树是否为二叉搜索树
// 第一个int为子的节点树
// 第二个为子树的最小值，第三个为子树的最大值
func ls(root *TreeNode) (int, int, int, bool) {
if root == nil {
return 0, -1 << 31, 1 << 31, true
}
if root.Left == nil && root.Right == nil {
return 1, root.Val, root.Val, true
}
left, lmin, lmax, ok1 := ls(root.Left)
right, rmin, rmax, ok2 := ls(root.Right)
if !ok1 || !ok2 {
// 有一个子树不是二叉搜索树
return max(left, right), 0, 0, false
}
// 之后为左右子树都是二叉搜索树
// 左姿势是二叉搜索树，但我不是
if root.Left != nil && lmax >= root.Val {
return max(left, right), 0, 0, false
}
// 右子树是二叉搜索树，但我不是
if root.Right != nil && rmin <= root.Val {
return max(left, right), 0, 0, false
}
// 左子树为nil
if root.Left == nil {
return 1 + right, root.Val, rmax, true
}
// 右子树为nil
if root.Right == nil {
return 1 + left, lmin, root.Val, true
}
// 左右都不为nil
return 1 + left + right, lmin, rmax, true
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
