Leaf-Similar Trees

Problem Description

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence. Two binary trees are considered leaf-similar if their leaf value sequence is the same. Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Key Insights

• A leaf node is defined as a node that has no children (both left and right child are null).
• The leaf value sequence can be obtained through a traversal of the tree (e.g., Depth-First Search).
• Two trees can be compared based on their leaf value sequences to determine if they are leaf-similar.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the larger of the two trees. Each node is visited once.
Space Complexity: O(H), where H is the height of the tree due to the recursion stack in depth-first traversal.

Solution

To determine if two binary trees are leaf-similar, we can utilize a depth-first search (DFS) approach to collect the leaf values of both trees. We will perform the following steps:

1. Define a helper function to perform a DFS on a tree and collect leaf values in a list.
2. Call this helper function for both trees (root1 and root2) to obtain their respective leaf value sequences.
3. Compare the two sequences. If they are equal, return true; otherwise, return false.

This approach efficiently captures the leaf values and compares them directly.

Code Solutions