325. Count the Leaves
Foundation1000 ms256 MBSolved by 0%
Print how many leaves the tree has. A leaf is a node with no children at all.
The distinction this problem exists for is between an ABSENT node and a leaf. Child 0 is not a leaf, it is nothing. A leaf is a real node whose two children both happen to be 0, and it contributes 1.
Getting that wrong gives twice the right answer, because every leaf has two absent children and each would be counted.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - The input always forms a valid tree rooted at node 1.
Input
The first line contains an integer n, the number of nodes.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains two integers, the left and right child of
node i, using 0 for no child. Node 1 is the root.
Output
Print one integer, the number of leaves.
Input3
2 1 3
2 3
0 0
0 0
Output2
Notehas two leaves, and a wrong base case reports four
Input1
7
0 0
Output1
Noteis a single node, which is itself a leaf
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution