1448. Count Good Nodes in Binary Tree
Explanation
To solve this problem, we can perform a depth-first search (DFS) traversal of the binary tree while keeping track of the maximum value encountered in the path from the root to the current node. If the current node's value is greater than or equal to the maximum value in the path, we increment the count of good nodes. We then recursively explore the left and right subtrees with the updated maximum value.
- Start the DFS traversal from the root node with an initial maximum value of Integer.MIN_VALUE.
- Keep track of the count of good nodes encountered during traversal.
- At each node, update the maximum value in the path if necessary and check if the current node is a good node.
- Recursively explore the left and right subtrees with the updated maximum value.
- Return the count of good nodes at the end of traversal.
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 binary tree (recursive stack space).
class Solution {
public int goodNodes(TreeNode root) {
return dfs(root, Integer.MIN_VALUE);
}
private int dfs(TreeNode node, int maxSoFar) {
if (node == null) {
return 0;
}
int count = 0;
if (node.val >= maxSoFar) {
count++;
maxSoFar = node.val;
}
count += dfs(node.left, maxSoFar);
count += dfs(node.right, maxSoFar);
return count;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.