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.
This 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.