Loading...
Loading...
Loading...
Anjali designs a rangoli as a tree of coloured dots. Each dot has a colour number and at most two dots below it. She wants the design to look exactly the same in a mirror held beside it.
The design is a mirror design when the left part of the tree is the flipped copy of the right part: same shape, same values, but left and right swapped at every step. Print YES or NO. An empty design counts as a mirror design.
N for no node. Children are listed only for real nodes, and N tokens at the end of the line may be left out. For example, 1 2 3 N 4 is root 1 with children 2 and 3, and 4 is the right child of 2. An empty tree is the single token N.YES if the tree is a mirror of itself, otherwise NO.Example 1
Input
1 2 2 3 4 4 3
Output
YES
The left part 2 → (3, 4) flipped is 2 → (4, 3), which is the right part.
Example 2
Input
1 2 2 N 3 N 3
Output
NO
Both 3s hang on the right. In a mirror one of them must hang on the left.
Try the problem first. Open one hint at a time.
Do not compare the tree with itself. Compare the left part with the right part.
Two parts are mirrors when their tops have equal values, and the outer children match and the inner children match.
The outer pair is left.left with right.right. The inner pair is left.right with right.left.
Two missing parts match. One missing and one present do not.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor