Approach 1: Depth First Search
Intuition and Algorithm
Let's find the leaf value sequence for both given trees. Afterwards, we can compare them to see if they are equal or not.
To find the leaf value sequence of a tree, we use a depth first search. Our
dfs function writes the node's value if it is a leaf, and then recursively explores each child. This is guaranteed to visit each leaf in left-to-right order, as left-children are fully explored before right-children.
Time Complexity: , where are the lengths of the given trees.
Space Complexity: , the space used in storing the leaf values.