Leaf Equivalent Trees

Given two binary trees root0 and root1, return whether the sequence of leaves left-to-right in both trees are the same.

Constraints

• n ≤ 100,000 where n is the number of nodes in root0
• m ≤ 100,000 where m is the number of nodes in root1

https://binarysearch.com/problems/Leaf-Equivalent-Trees

Examples

Example 1

Input

• root0 =

• root1 =

Output

• answer = False

Explanation

The left tree has [2, 3] and right has [3, 2]

Example 2

Input

• root0 =

• root1 =

Output

• answer = True

Explanation

Both trees have leaves [2, 1].

Solution