Dare2Solve
Given a binary tree, a node is considered a "good" node if the value of the node is greater than or equal to the maximum value in the path from the root to that node. The task is to count the number of good nodes in the tree.
The intuition behind solving this problem is to traverse the tree while keeping track of the maximum value encountered along the current path. A node is considered "good" if its value is greater than or equal to this maximum value. We need to traverse the entire tree and count how many such nodes exist.
O(N), where N is the number of nodes in the tree. Each node is visited once.
O(H), where H is the height of the tree. This is the space required by the call stack or the stack used for iterative traversal.
/**
* Definition for a binary tree node.
* 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 goodNodes(TreeNode* root) {
if (!root) return 0;
int numGoodNodes = 0;
stack<pair<TreeNode*, int>> st;
st.push({root, INT_MIN});
while (!st.empty()) {
auto [node, maxVal] = st.top();
st.pop();
if (node->val >= maxVal) {
numGoodNodes += 1;
maxVal = node->val;
}
if (node->right) st.push({node->right, maxVal});
if (node->left) st.push({node->left, maxVal});
}
return numGoodNodes;
}
};
class Solution:
def goodNodes(self, root: TreeNode) -> int:
if not root:
return 0
num_good_nodes = 0
stack = [(root, float('-inf'))]
while stack:
node, max_val = stack.pop()
if node.val >= max_val:
num_good_nodes += 1
max_val = node.val
if node.left:
stack.append((node.left, max_val))
if node.right:
stack.append((node.right, max_val))
return num_good_nodes
class Solution {
public int goodNodes(TreeNode root) {
if (root == null) return 0;
int numGoodNodes = 0;
Deque<Pair<TreeNode, Integer>> stack = new ArrayDeque<>();
stack.push(new Pair<>(root, Integer.MIN_VALUE));
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> current = stack.pop();
TreeNode node = current.getKey();
int maxVal = current.getValue();
if (node.val >= maxVal) {
numGoodNodes += 1;
maxVal = node.val;
}
if (node.right != null) stack.push(new Pair<>(node.right, maxVal));
if (node.left != null) stack.push(new Pair<>(node.left, maxVal));
}
return numGoodNodes;
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var goodNodes = function (root) {
if (!root) return 0;
let numGoodNodes = 0;
const stack = [];
stack.push([root, -Infinity]);
while (stack.length) {
let [node, max] = stack.pop();
const { left, right, val } = node;
if (max <= val) {
numGoodNodes += 1;
max = val;
}
if (left) stack.push([left, max]);
if (right) stack.push([right, max]);
}
return numGoodNodes;
};