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