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.
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
int dfs(TreeNode* node, int maxVal) {
if (!node) return 0;
int good = 0;
if (node->val >= maxVal) good = 1;
maxVal = max(maxVal, node->val);
return good + dfs(node->left, maxVal) + dfs(node->right, maxVal);
}
int goodNodes(TreeNode* root) {
return dfs(root, root->val);
}
};
This 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.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5 public int val;
6 public TreeNode left;
7 public TreeNode right;
8 public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
9 this.val = val;
10 this.left = left;
11 this.right = right;
12 }
13}
14
15public class Solution {
16 public int GoodNodes(TreeNode root) {
17 if (root == null) return 0;
18 Queue<(TreeNode, int)> queue = new Queue<(TreeNode, int)>();
19 queue.Enqueue((root, root.val));
20 int goodCount = 0;
21 while (queue.Count > 0) {
22 (TreeNode node, int maxVal) = queue.Dequeue();
23 if (node.val >= maxVal) goodCount++;
24 if (node.left != null) queue.Enqueue((node.left, Math.Max(maxVal, node.val)));
25 if (node.right != null) queue.Enqueue((node.right, Math.Max(maxVal, node.val)));
26 }
27 return goodCount;
28 }
29}
30In this C# solution, a queue is used to implement BFS, with each item being a tuple that contains both the current node and the maximum value encountered so far. The process checks each node, updating the count of good nodes as necessary.