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

类型：树

• 1448. 统计二叉树中好节点的数目 💛

  https://leetcode-cn.com/problems/count-good-nodes-in-binary-tree/

  ❓ 二叉树中，好结点 X 定义为，从根到该结点的路径中，没有任何结点的值大于 X 的值。

  求计算二叉树中好结点的数目。

  💡 DFS

  我们在 DFS 的过程中，维护当前路径中的最大值即可。

  class Solution:
  
      def goodNodes(self, root: TreeNode) -> int:
          if not root:
              return 0
  
          def dfs(node, max_val):
              if not node:
                  return 0
              count = 0
              if node.val >= max_val:
                  count = 1
                  max_val = node.val
              return count + dfs(node.left, max_val) + dfs(node.right, max_val)
  
          return dfs(root, root.val)

  时间复杂度：O(n)，空间复杂度：O(h)