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 <iostream>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode() : val(0), left(nullptr), right(nullptr) {}
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15 int dfs(TreeNode* node, int maxVal) {
16 if (!node) return 0;
17 int good = 0;
18 if (node->val >= maxVal) good = 1;
19 maxVal = max(maxVal, node->val);
20 return good + dfs(node->left, maxVal) + dfs(node->right, maxVal);
21 }
22
23 int goodNodes(TreeNode* root) {
24 return dfs(root, root->val);
25 }
26};
27This C++ solution uses a member function dfs of the Solution class to recursively traverse the tree and count the good nodes based on the maximum value constraint.
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.