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.
The Java solution implements a BFS approach using a queue, where each element is a pair of a node and its corresponding maximum value encountered from the root. It iteratively processes nodes while maintaining the count of good nodes.