347. Nodes With Two Children
Foundation1000 ms256 MBSolved by 0%
Print how many nodes have BOTH a left child and a right child.
Three categories exist in a binary tree: nodes with two children, nodes with exactly one, and leaves with none. This problem counts the first, and the next one counts the second.
There is a fact worth checking your answer against. In any binary tree, the number of leaves is always exactly one more than the number of nodes with two children.
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 nodes with two children.
Input7
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
Output3
Noteis a full tree, where every internal node has two children
Input1
7
0 0
Output0
Noteis a single node with no children at all
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution