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.
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 const dfs = (node, maxVal) => {
9 if (!node) return 0;
10 let good = 0;
11 if (node.val >= maxVal) good = 1;
12 maxVal = Math.max(maxVal, node.val);
13 good += dfs(node.left, maxVal);
14 good += dfs(node.right, maxVal);
15 return good;
16 };
17 return dfs(root, root.val);
18};
19This JavaScript solution defines a DFS function inline and is called recursively with the maximum value found on the path as a parameter. The function calculates the number of good nodes during the traversal.
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.