Leaf-Similar Trees - Solution & Explanation

This approach involves using a recursive depth-first search (DFS) to traverse each binary tree and collect the leaf node values by diving into each sub-tree starting from the root node. We store the values of all leaf nodes from left to right in a list. After extracting the sequences from both trees, we compare these sequences to determine if the trees are leaf-similar.

We define a nested function dfs inside our main function to recursively traverse the binary tree. The dfs function returns a list of leaf node values by first checking if a node is null (in which case it returns an empty list), then it checks if the node is a leaf node (no left and right children), and if so, it returns a list containing the node's value. Otherwise, it recursively calls itself on the left and right children and concatenates their results. Lastly, we compare the two leaf sequences to decide if the trees are leaf-similar.

This method employs an iterative version of depth-first search utilizing a stack to collect leaves of the tree. By substituting recursion with a stack, we manually handle tree traversal, but the core logic remains similar: traverse each tree, collect leaves, and compare leaf sequences.

Here, a Stack is used for both implementing the DFS traversal and collecting leaf node values iteratively. For leaf nodes, their values are added to a separate stack (list) leaves. By performing this for both root1 and root2, we get their leaf sequences, which are compared for equality at the end.