Leaf-Similar Trees

To determine whether two binary trees are leaf-similar, we need to compare the leaf value sequences of both trees. If they are the same, the trees are considered leaf-similar.

Here is a step-by-step explanation:

  1. Find the Leaf Value Sequence for Each Tree: For both trees, we need to traverse the tree and collect the values of the leaf nodes (nodes that do not have left or right children). A depth-first traversal (such as inorder) will work for this purpose.

  2. Compare the Leaf Value Sequences: Once we have the leaf value sequences for both trees, we can compare them to determine if they are the same.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def getLeafSequence(root):
            if root is None:
                return []
            if root.left is None and root.right is None:
                return [root.val]
            return getLeafSequence(root.left) + getLeafSequence(root.right)

        leaf_seq1 = getLeafSequence(root1)
        leaf_seq2 = getLeafSequence(root2)

        return leaf_seq1 == leaf_seq2

Explanation:

  • The function getLeafSequence is a recursive function that traverses the tree in a depth-first manner and returns the leaf value sequence. If the node is a leaf node (i.e., it does not have left or right children), it returns a list with its value. Otherwise, it recursively traverses the left and right children.

  • We call getLeafSequence for both root1 and root2 to get their respective leaf value sequences, and then we compare them to determine if they are the same.

The time complexity of this solution is (O(n + m)), where (n) and (m) are the numbers of nodes in the first and second trees, respectively. The space complexity is also (O(n + m)), due to the storage needed for the leaf sequences and the recursion stack.