2445. Number of Nodes With Value One
Explanation
To solve this problem, we will traverse the given binary tree in a post-order manner. At each node, we will calculate the number of nodes with value 1 in the left and right subtrees. Then, we will update the count of nodes with value 1 in the current subtree and return this count to the parent node.
We will define a recursive function that takes a node as input and returns the count of nodes with value 1 in the subtree rooted at that node.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public int countNodesWithOne(TreeNode root) {
if (root == null) {
return 0;
}
int[] count = new int[1];
countNodes(root, count);
return count[0];
}
private int countNodes(TreeNode node, int[] count) {
if (node == null) {
return 0;
}
int leftCount = countNodes(node.left, count);
int rightCount = countNodes(node.right, count);
if (node.val == 1) {
count[0]++;
}
return leftCount + rightCount + (node.val == 1 ? 1 : 0);
}
}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.