348. Nodes With Exactly One Child
Foundation1000 ms256 MBSolved by 0%
Print how many nodes have exactly one child, on either side.
The condition is an EXCLUSIVE or: one child present and the other absent. A node with two children does not count and neither does a leaf.
Together with the previous two problems this partitions the tree: every node is a
leaf, has one child, or has two, and the three counts add up to n. That is a
good check on all three answers.
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 exactly one child.
Input4
1 2 3 4
0 2
0 3
0 4
0 0
Output3
Noteis a chain, where every node except the last has one child
Input7
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
Output0
Noteis a full tree, where no node has exactly one child
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution