1448. Count Good Nodes in Binary Tree
## description
## 1448. Count Good Nodes in Binary Tree
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:
1Input: root = [3,1,4,3,null,1,5]
2Output: 4
3Explanation: Nodes in blue are good.
4Root Node (3) is always a good node.
5Node 4 -> (3,4) is the maximum value in the path starting from the root.
6Node 5 -> (3,4,5) is the maximum value in the path
7Node 3 -> (3,1,3) is the maximum value in the path.Example 2:
1Input: root = [3,3,null,4,2]
2Output: 3
3Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.Example 3:
1Input: root = [1]
2Output: 1
3Explanation: Root is considered as good.- –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].
Constraints:
## notes
### Intuition
Keep track of the largest node seen in the path.
### Implementation
Since we are going down the path, we use DFS. Define our recursive function to the node and a max value parameter. Base case is if the root is null, return. Otherwise, check if max value is less than or equal to the current node's value (i.e. the node is larger or equal to the largest value seen before this in its path), if true, increment the good nodes counter. Call the DFS function on left and right side taking the max of the current max value and the node's value.
- –Time: O(n), each node is processed once
- –Space: O(n), call stack
### Complexity
## solution
1from typing import Optional
2from lcutils import TreeNode
3
4# Definition for a binary tree node.
5# class TreeNode:
6# def __init__(self, val=0, left=None, right=None):
7# self.val = val
8# self.left = left
9# self.right = right
10class Solution:
11 def goodNodes(self, root: TreeNode) -> int:
12 good_nodes = 0
13 def dfs(node: Optional[TreeNode], max_val: int):
14 nonlocal good_nodes
15 if not node:
16 return
17 if max_val <= node.val:
18 good_nodes += 1
19 dfs(node.right, max(max_val, node.val))
20 dfs(node.left, max(max_val, node.val))
21
22 dfs(root, root.val)
23 return good_nodes
24
25
26
27
28if __name__ == "__main__":
29 # Include one-off tests here or debugging logic that can be run by running this file
30 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
31 solution = Solution()
32