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.
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
private int Dfs(TreeNode node, int maxVal) {
if (node == null) return 0;
int good = (node.val >= maxVal) ? 1 : 0;
maxVal = Math.Max(maxVal, node.val);
good += Dfs(node.left, maxVal);
good += Dfs(node.right, maxVal);
return good;
}
public int GoodNodes(TreeNode root) {
return Dfs(root, root.val);
}
}
This C# implementation defines a private recursive method Dfs that is called from the public method GoodNodes. It counts the nodes that are considered good.
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.
1function TreeNode(val, left, right) {
2 this.val = (val===undefined ? 0 : val)
3 this.left = (left===undefined ? null : left)
4 this.right = (right===undefined ? null : right)
5}
6
7const goodNodes = function(root) {
8 if (!root) return 0;
9 const queue = [{ node: root, maxVal: root.val }];
10 let goodCount = 0;
11 while (queue.length) {
12 const { node, maxVal } = queue.shift();
13 if (node.val >= maxVal) goodCount++;
14 if (node.left) queue.push({ node: node.left, maxVal: Math.max(maxVal, node.val) });
15 if (node.right) queue.push({ node: node.right, maxVal: Math.max(maxVal, node.val) });
16 }
17 return goodCount;
18};
19This JavaScript solution applies an iterative BFS approach using an array as the queue. Each object in the queue contains the current node and its max value, and during traversal, it checks and updates the count of good nodes.