LeetCode 题解工作台
统计二叉树中好节点的数目
给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。 「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。 示例 1： 输入： root = [3,1,4,3,null,1,5] 输出： 4 解释： 图中蓝色节点为好节点。 根节点 (3) 永远是个好节…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们设计一个函数 $dfs(root, mx)$，表示从当前节点 开始搜索好节点，其中 表示从根节点到当前节点的路径（不包括当前节点）上的最大值。 函数 $dfs(root, mx)$ 的执行逻辑如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。
「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。
示例 1：
输入：root = [3,1,4,3,null,1,5] 输出：4 解释：图中蓝色节点为好节点。 根节点 (3) 永远是个好节点。 节点 4 -> (3,4) 是路径中的最大值。 节点 5 -> (3,4,5) 是路径中的最大值。 节点 3 -> (3,1,3) 是路径中的最大值。
示例 2：
输入：root = [3,3,null,4,2] 输出：3 解释：节点 2 -> (3, 3, 2) 不是好节点，因为 "3" 比它大。
示例 3：
输入：root = [1] 输出：1 解释：根节点是好节点。
提示：
- 二叉树中节点数目范围是
[1, 10^5]。 - 每个节点权值的范围是
[-10^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 goodNodes(self, root: TreeNode) -> int:
def dfs(root: TreeNode, mx: int):
if root is None:
return
nonlocal ans
if mx <= root.val:
ans += 1
mx = root.val
dfs(root.left, mx)
dfs(root.right, mx)
ans = 0
dfs(root, -1000000)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each node is visited once. Space complexity is O(h) for DFS recursion or stack, where h is the tree height, and O(n) for BFS queue in the worst case. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if candidates correctly track the maximum along the path.
- question_mark
Notice if they handle edge cases with negative or duplicate values.
- question_mark
See if they choose DFS or BFS and justify stack versus queue use.
常见陷阱
外企场景- error
Failing to update the path maximum when descending to child nodes.
- error
Counting nodes incorrectly when values equal the current path maximum.
- error
Using recursion without considering deep trees causing stack overflow.
进阶变体
外企场景- arrow_right_alt
Count nodes where the path maximum must be strictly less than the current node.
- arrow_right_alt
Return the list of good node values instead of just the count.
- arrow_right_alt
Apply the same path-max check in an N-ary tree instead of a binary tree.