Sponsored
Sponsored
Time Complexity: O(n), where n is the number of nodes in the binary tree.
Space Complexity: O(h), where h is the height of the tree due to the recursion stack.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def dfs(self, node, maxVal):
9 if not node:
10 return 0
11 good = 1 if node.val >= maxVal else 0
12 maxVal = max(maxVal, node.val)
13 return good + self.dfs(node.left, maxVal) + self.dfs(node.right, maxVal)
14
15 def goodNodes(self, root):
16 return self.dfs(root, root.val)
17This Python solution utilizes a helper function dfs within the class Solution. It employs recursion to traverse the tree and count the good nodes as per the conditions provided.
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(w), where w is the maximum width of the tree.
The C solution implements an iterative BFS using a custom queue structure. Each item in the queue stores a node and the maximum value along the path from the root to that node. The algorithm iterates over the queue, evaluating each node's value against the max value, updating good nodes count accordingly.