💬 Discord
Sign In
NeetCode #396LC-872EasyTrees
← Back to All Problems

#396 · #872 · Leaf-Similar Trees(叶子相似的树)

📌 Problem Statement & Constraints

Consider all the leaves of a binary tree, from left to right, forming a sequence. Two trees are leaf-similar if their leaf sequences are identical. Given the roots of two trees, return whether they are leaf-similar. Constraints: the number of nodes in each tree is in [1, 200].

💡 Core Algorithmic Approaches

  1. Collect the leaf values of each tree with a DFS that visits the left child first.
  2. Compare the two sequences.
  3. The left-first order is essential, since the sequence is defined left to right.
  4. Comparing incrementally (with generators or early exit) saves memory but is rarely necessary at these limits.

💻 Benchmark Python3 Implementation

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def leaves(node: Optional[TreeNode]) -> List[int]:
            if not node:
                return []
            if not node.left and not node.right:
                return [node.val]          # a leaf
            return leaves(node.left) + leaves(node.right)   # left to right

        return leaves(root1) == leaves(root2)


# Generator variant: compares lazily, without materialising the lists
class Solution2:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def gen(node: Optional[TreeNode]):
            if not node:
                return
            if not node.left and not node.right:
                yield node.val
                return
            yield from gen(node.left)
            yield from gen(node.right)

        return list(gen(root1)) == list(gen(root2))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m + n): each tree is traversed once.
💾 Space Complexity
O(h) for the recursion plus O(number of leaves) for the lists.

⚠️ Interview Pitfalls & Follow-ups

  • Visiting the right child first: the sequence would be right to left and would not match the definition.
  • Counting all nodes instead of leaves: only leaf values form the sequence.
  • Assuming the trees must have the same shape: only the leaf sequences must match.
  • Using a single shared list for both trees: each tree needs its own sequence.