【Leetcode Daily】1448统计二叉树中好节点的数目

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是规定，一个二叉树节点，如果根节点到这个节点的路上没有比节点值更大的点，那么这个点就是好节点，求好节点数目。

思路分享

• 直接 dfs，路上记录当前遍历到的最大值，比较当前节点的值是否大于等于这个值，如果是，那就是好节点。

• 灵神采用递归方式，先递归下去，带上当前遍历最大值，最后返回值时再结算当前是否是好节点。

  https://leetcode.cn/problems/count-good-nodes-in-binary-tree/solutions/2403677/jian-ji-xie-fa-pythonjavacgojs-by-endles-gwxt/

代码解答（强烈建议自行解答后再看）

• 参考题解

# 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(root: Optional[TreeNode], cur_max: int):
            if not root:
                return
            if root.val >= cur_max:
                nonlocal ans
                ans += 1
            cur_max = max(cur_max, root.val)
            dfs(root.left, cur_max)
            dfs(root.right, cur_max)
        dfs(root, root.val)
        return ans