难度: Medium
Submission
运行时间: 26 ms
内存: 18.1 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:
max_nums = 0
def dfs(node):
nonlocal max_nums
if node is None:
return None
left_ret = dfs(node.left)
right_ret = dfs(node.right)
if left_ret is None and right_ret is None:
# leaf node
is_bst = True
cur_num = 1
max_val = node.val
min_val = node.val
max_nums = max(max_nums, cur_num)
return is_bst, min_val, max_val, cur_num
elif left_ret and right_ret:
if left_ret[0] and right_ret[0] and node.val > left_ret[2] and node.val < right_ret[1]:
is_bst = True
cur_num = 1 + left_ret[-1] + right_ret[-1]
max_val = right_ret[2]
min_val = left_ret[1]
max_nums = max(max_nums, cur_num)
return is_bst, min_val, max_val, cur_num
elif left_ret:
if left_ret[0] and node.val > left_ret[2]:
is_bst = True
cur_num = 1 + left_ret[-1]
min_val = left_ret[1]
max_val = node.val
max_nums = max(max_nums, cur_num)
return is_bst, min_val, max_val, cur_num
elif right_ret:
if right_ret[0] and node.val < right_ret[1]:
is_bst = True
cur_num = 1 + right_ret[-1]
min_val = node.val
max_val = right_ret[2]
max_nums = max(max_nums, cur_num)
return is_bst, min_val, max_val, cur_num
return False, None, None, None
dfs(root)
return max_nums
Explain
该题解使用深度优先遍历（DFS）的方法来遍历二叉树的每个节点。对于每个节点，判断其是否能成为一个二叉搜索树（BST）的根节点。如果当前节点能成为BST的根，那么以该节点为根的子树就是一个BST，记录其节点数，并与当前最大BST节点数比较，更新最大值。DFS函数返回一个元组，包含当前子树是否为BST、子树的最小值、最大值和节点数。通过比较当前节点与其左右子树的最大最小值，可以判断当前节点是否能成为BST的根。
时间复杂度: O(n)
空间复杂度: O(h)，最坏情况下O(n)，平均情况下O(logn)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:
max_nums = 0
def dfs(node):
nonlocal max_nums
if node is None:
return None
# 递归遍历左子树
left_ret = dfs(node.left)
# 递归遍历右子树
right_ret = dfs(node.right)
if left_ret is None and right_ret is None:
# 当前节点为叶子节点
is_bst = True
cur_num = 1
max_val = node.val
min_val = node.val
max_nums = max(max_nums, cur_num)
return is_bst, min_val, max_val, cur_num
elif left_ret and right_ret:
# 当前节点的左右子树都存在
if left_ret[0] and right_ret[0] and node.val > left_ret[2] and node.val < right_ret[1]:
# 如果左右子树都是BST，且当前节点的值在左子树最大值和右子树最小值之间，则当前节点也是BST的根
is_bst = True
cur_num = 1 + left_ret[-1] + right_ret[-1]
max_val = right_ret[2]
min_val = left_ret[1]
max_nums = max(max_nums, cur_num)
return is_bst, min_val, max_val, cur_num
elif left_ret:
# 只存在左子树
if left_ret[0] and node.val > left_ret[2]:
# 如果左子树是BST，且当前节点的值大于左子树的最大值，则当前节点也是BST的根
is_bst = True
cur_num = 1 + left_ret[-1]
min_val = left_ret[1]
max_val = node.val
max_nums = max(max_nums, cur_num)
return is_bst, min_val, max_val, cur_num
elif right_ret:
# 只存在右子树
if right_ret[0] and node.val < right_ret[1]:
# 如果右子树是BST，且当前节点的值小于右子树的最小值，则当前节点也是BST的根
is_bst = True
cur_num = 1 + right_ret[-1]
min_val = node.val
max_val = right_ret[2]
max_nums = max(max_nums, cur_num)
return is_bst, min_val, max_val, cur_num
return False, None, None, None
dfs(root)
return max_nums
Explore
在DFS的返回值中，元组包含四个部分：(is_bst, min_val, max_val, cur_num)。其中，is_bst是一个布尔值，表示当前子树是否为二叉搜索树；min_val是当前子树中的最小值；max_val是当前子树中的最大值；cur_num是当前子树的节点数。使用这些信息来判断一个节点是否能成为BST的根节点时：首先检查左右子树是否分别是BST（即左右子树的is_bst都为True），然后确保当前节点的值大于左子树的最大值且小于右子树的最小值。如果这些条件都满足，当前节点可以成为BST的根节点。
题解中提到的条件是：左子树的所有节点值都必须小于当前节点的值，右子树的所有节点值都必须大于当前节点的值。这些条件是必须的，因为二叉搜索树的定义要求任一节点的左子树只包含小于当前节点的值的节点，右子树只包含大于当前节点的值的节点。只有当这些条件被满足时，整个树结构才能维持BST的性质。
在只有左子树的情况下，题解确保当前节点的值大于左子树的最大值，这符合BST的性质，即所有左侧节点的值必须小于根节点的值。在只有右子树的情况下，确保当前节点的值小于右子树的最小值，这同样符合BST的性质，即所有右侧节点的值必须大于根节点的值。通过这种方式，题解确保了即使只有一侧子树存在时，当前节点与其子树的值也能满足BST的基本要求。
如果当前节点的左子树或右子树不是BST（即is_bst为False），则当前节点本身也不能成为BST的根节点。在这种情况下，我们不会尝试将当前节点作为BST的根，而是直接返回False以及无效的最小值和最大值。这样做是因为，如果任何子树不满足BST的性质，那么整个包含该子树的更大的树也不能是BST。