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