LeetCode 题解工作台
二叉搜索子树的最大键值和
给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。 二叉搜索树的定义如下： 任意节点的左子树中的键值都 小于 此节点的键值。 任意节点的右子树中的键值都 大于 此节点的键值。 任意节点的左子树和右子树都是二叉搜索树。 示例 1： 输入： root = [1,4,3,2…
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 二分·树·traversal
答案摘要
判断一棵树是否是二叉搜索树，需要满足以下四个条件： - 左子树是二叉搜索树；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。
二叉搜索树的定义如下：
- 任意节点的左子树中的键值都 小于 此节点的键值。
- 任意节点的右子树中的键值都 大于 此节点的键值。
- 任意节点的左子树和右子树都是二叉搜索树。
示例 1：
输入：root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6] 输出：20 解释：键值为 3 的子树是和最大的二叉搜索树。
示例 2：
输入：root = [4,3,null,1,2] 输出：2 解释：键值为 2 的单节点子树是和最大的二叉搜索树。
示例 3：
输入：root = [-4,-2,-5] 输出：0 解释：所有节点键值都为负数，和最大的二叉搜索树为空。
示例 4：
输入：root = [2,1,3] 输出：6
示例 5：
输入：root = [5,4,8,3,null,6,3] 输出：7
提示：
- 每棵树有
1到40000个节点。 - 每个节点的键值在
[-4 * 10^4 , 4 * 10^4]之间。
解题思路
方法一：DFS
判断一棵树是否是二叉搜索树，需要满足以下四个条件：
- 左子树是二叉搜索树；
- 右子树是二叉搜索树；
- 左子树的最大值小于根节点的值；
- 右子树的最小值大于根节点的值。
因此，我们设计一个函数 ，函数的返回值是一个四元组 ，其中：
- 数字 表示以 为根的树是否是二叉搜索树。如果是二叉搜索树，则 ；否则 ；
- 数字 表示以 为根的树的最小值；
- 数字 表示以 为根的树的最大值；
- 数字 表示以 为根的树的所有节点的和。
函数 的执行逻辑如下：
如果 为空节点，则返回 ，表示空树是二叉搜索树，最小值和最大值分别为正无穷和负无穷，节点和为 。
否则，递归计算 的左子树和右子树，分别得到 和 ，然后判断 节点是否满足二叉搜索树的条件。
如果满足 且 且 ，则以 为根的树是二叉搜索树，节点和 。我们更新答案 ，并返回 。
否则，以 为根的树不是二叉搜索树，我们返回 。
我们在主函数中调用 ，执行完毕后，答案即为 。
时间复杂度 ，空间复杂度 。其中 是二叉树的节点数。
# 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 maxSumBST(self, root: Optional[TreeNode]) -> int:
def dfs(root: Optional[TreeNode]) -> tuple:
if root is None:
return 1, inf, -inf, 0
lbst, lmi, lmx, ls = dfs(root.left)
rbst, rmi, rmx, rs = dfs(root.right)
if lbst and rbst and lmx < root.val < rmi:
nonlocal ans
s = ls + rs + root.val
ans = max(ans, s)
return 1, min(lmi, root.val), max(rmx, root.val), s
return 0, 0, 0, 0
ans = 0
dfs(root)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for understanding of tree traversal and state tracking during DFS.
- question_mark
Assess the candidate's ability to manage multiple parameters (sum, validity, min, max) during traversal.
- question_mark
Check if the candidate optimizes the solution by avoiding unnecessary recalculations.
常见陷阱
外企场景- error
Failing to track the minimum and maximum values of subtrees can lead to incorrect validation of the BST.
- error
Not considering the case where no valid BST exists and returning an incorrect sum.
- error
Inefficient or incorrect recursive calls can lead to excessive time complexity, especially in large trees.
进阶变体
外企场景- arrow_right_alt
Consider adding additional constraints like limiting the maximum tree depth to test efficiency.
- arrow_right_alt
Adapt the problem for trees that contain duplicate values and check how BST validation is handled.
- arrow_right_alt
Extend the problem to consider the maximum sum for subtrees with specific node value constraints.