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 Java solution implements a BFS approach using a queue, where each element is a pair of a node and its corresponding maximum value encountered from the root. It iteratively processes nodes while maintaining the count of good nodes.