统计二叉树中好节点的数目-LeetCode

统计二叉树中好节点的数目

🎯 问题描述

给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。
「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值（即当前节点的值，是从根到该节点路径上的最大值）。

💻 解题思路

思路：DFS 深度优先搜索（带状态传递）

核心思想：在从根节点向下遍历的过程中，我们需要时刻记录“从根节点到当前节点路径上遇到的最大值”。如果当前节点的值大于等于这个最大值，它就是一个好节点。

代码实现

from typing import Optional

# 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: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node, x):
            if node is None:
                return
            nonlocal ans
            # 如果当前节点的值 >= 路径上的历史最大值，则为好节点
            if node.val >= x:
                ans += 1
            # 更新路径上的最大值，传递给下一层
            x = max(x, node.val)
            dfs(node.left, x)
            dfs(node.right, x)
        
        # 初始最大值设为负无穷，保证根节点一定会被计入
        dfs(root, float('-inf'))
        return ans

📊 性能分析

• 时间复杂度：$O(n)$。其中 $n$ 是二叉树的节点数量，每个节点只会被访问一次。
• 空间复杂度：$O(h)$。取决于递归调用栈的深度，即二叉树的高度 $h$。

💡 思考

这道题与普通的二叉树遍历最大的区别在于**“路径状态的维护”**。

• 普通的遍历（如求深度、求和）只需要关注当前节点。
• 而这道题要求我们像“登山”一样，每走一步都要记录沿途经过的“最高海拔”（路径最大值）。
• 初始值设为 float('-inf') 是一个非常实用的编程小技巧，能完美处理根节点以及节点值为负数的情况。