0
.
Example: 1 / \ 2 3 / \ / \ 4 5 6 7 / 8 Half nodes count => 1
Queue
and increment a count
variable if a half node is encountered.
1. Initialize a Queue
to store the nodes of the tree.
2. Add the root
node to the Queue.
3. Loop
until the Queue
becomes empty.
4. Within the loop, remove the node from the Queue
and check if it has exactly one child.
5. If yes, increment the count
, which stores the total number of half nodes.
6. Enqueue the children of the above node.
7. At the end of the loop
, return the count
.
public int numberOfHalfNodes(TreeNode root) { }
C
Java
Python