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 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode() {}
6 TreeNode(int val) { this.val = val; }
7 TreeNode(int val, TreeNode left, TreeNode right) {
8 this.val = val;
9 this.left = left;
10 this.right = right;
11 }
12}
13
14class Solution {
15 private int dfs(TreeNode node, int maxVal) {
16 if (node == null) return 0;
17 int count = 0;
18 if (node.val >= maxVal) count = 1;
19 maxVal = Math.max(maxVal, node.val);
20 count += dfs(node.left, maxVal);
21 count += dfs(node.right, maxVal);
22 return count;
23 }
24
25 public int goodNodes(TreeNode root) {
26 return dfs(root, root.val);
27 }
28}
29This Java implementation uses a helper method dfs encapsulated in the Solution class, which recursively traverses the binary tree and counts good nodes.
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 Python solution makes use of a deque from the collections module to implement the BFS. Each dequeued element is a tuple of the current node and the maximum value seen from the root to that node, allowing proper evaluation and update of the good nodes count.