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.
1#include <stdlib.h>
2#include <stdio.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10int dfs(struct TreeNode* node, int maxVal) {
11 if (!node) return 0;
12 int total = 0;
13 if (node->val >= maxVal) total = 1;
14 maxVal = (node->val > maxVal) ? node->val : maxVal;
15 total += dfs(node->left, maxVal);
16 total += dfs(node->right, maxVal);
17 return total;
18}
19
20int goodNodes(struct TreeNode* root) {
21 if (!root) return 0;
22 return dfs(root, root->val);
23}
24This solution defines a helper function dfs that performs the depth-first search. It takes parameters for the current node and the maximum value encountered so far. It returns the total count of 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.
1
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.