<div>
Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.
Return the number of good nodes in the binary tree.
Example 1:
<pre>Input: root = [3,1,4,3,null,1,5] Output: 4 Explanation: Nodes in blue are good. Root Node (3) is always a good node. Node 4 -> (3,4) is the maximum value in the path starting from the root. Node 5 -> (3,4,5) is the maximum value in the path Node 3 -> (3,1,3) is the maximum value in the path.</pre>
Example 2:
<pre>Input: root = [3,3,null,4,2] Output: 3 Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.</pre>
Example 3:
<pre>Input: root = [1] Output: 1 Explanation: Root is considered as good.</pre>
Constraints:
- The number of nodes in the binary tree is in the range
[1, 10^5]. - Each node's value is between
[-10^4, 10^4].
</div>
题目大意：
一个节点是good表示该节点从root到自己的路径上，所有节点都小于等于自己。求二叉树的good节点个数
解题思路：
统计左右子树的good节点个数，最重要是引入类似于min, max验证BST，引入path_max来记录路径上的最大值，只要该节点值大于path_max就是good节点。DFS返回good节点个数
解题步骤：
N/A
注意事项：
- 引入path_max来记录路径上的最大值
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12def goodNodes(self, root: TreeNode) -> int:
return self.dfs(root, float('-inf'))
def dfs(self, root, path_max):
if not root:
return 0
left = self.dfs(root.left, max(root.val, path_max))
right = self.dfs(root.right, max(root.val, path_max))
res = left + right
if path_max <= root.val:
res += 1
return res
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
