A hanging mobile sculpture is a binary tree of joints. Define the height of a sub-mobile as the number of joints on the longest path from that joint straight down to a dangling end; an empty side has height 0, and a single joint with nothing below it has height 1.
A joint is a tilt fault if the heights of its left and right sub-mobiles differ by more than 1 (that is, their absolute difference is at least 2). Report how many joints are tilt faults.
Line 1: an integer k, the number of tokens on line 2.
Line 2: k space-separated tokens giving the tree in level order. The first token is the root; each subsequent token is an integer label or null for a missing child. Children of null nodes are omitted. (Labels do not affect the answer.)
A single integer: the number of tilt-fault joints.
Example 1
Input
4 1 2 null 3
Expected
1
Explanation
The root's left sub-mobile is the chain 2->3 (height 2) and its right side is empty (height 0); the difference 2 is more than 1, so the root is a fault. Node 2 has heights 1 and 0 (fine), and node 3 is a single joint (0 and 0). One fault.
Example 2
Input
3 1 2 3
Expected
0
Explanation
The root has two single-joint children, heights 1 and 1, difference 0. No joint is a fault, so the answer is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →