Solution
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 lefttoright order, as leftchildren are fully explored before rightchildren.
Complexity Analysis

Time Complexity: , where are the lengths of the given trees.

Space Complexity: , the space used in storing the leaf values.