LC872 Leaf-Similar Trees 🟢

This matches the "collect then compare" pattern — walk the maze, fill boxes with dead ends, then check if the two boxes match.

1. Problem Decoding

We have two Binary Trees (root1 and root2).
Mission: walk in and collect Leaf Node values (tip nodes with no children), left to right.

If the leaf list of the first tree matches the second tree position-by-position, return True; otherwise False.

2. Mental Model

Picture the Tree as a "maze":

• Root: the entrance door
• Node: a fork / junction
• Leaf: a "dead end" (nowhere left or right to go)

We'll use DFS (Depth-First Search) with these maze rules:

1. Always turn left first
2. When you hit a "dead end (Leaf)", put the wall number in the box (List), then walk back (Return)
3. Back at the fork, then explore the right branch

3. Logic-to-Code Mapping

We'll write get_leaves(node) to walk the maze, handling three situations:

Situation 1: Fall off the edge (no branch)

When a branch doesn't exist, the computer sees Null / None. Tell it: "nothing to collect — send back an empty box."

# If node is empty (this branch doesn't exist)
if not node:
    return []  # send back an empty List

Situation 2: Dead end (it's a Leaf!)

Our main goal! A dead end means the Node you're on has no left child and no right child. Put this Node's number in the box and return it upward.

# No left child and no right child
if not node.left and not node.right:
    return [node.val]  # put the number in a List and Return

Situation 3: A fork (keep exploring)

If it's not a dead end, it's a fork. Rule: "left first, then right." Recurse left, then right, then pour the boxes together (Python + concatenates Lists).

# Take the left box, concatenate the right box
return get_leaves(node.left) + get_leaves(node.right)

4. Step-by-Step Walkthrough

Suppose the Tree looks like this, and we call get_leaves:

        3
       / \
      5   1
     / \
    6   2

1. Start (Root): Node 3 — not a dead end → Situation 3: "left box + right box", dive to node.left (5)
2. Left branch: Node 5 — not a dead end, dive left again (to 6)
3. First Leaf!: Node 6 — Situation 2 → box [6], Return up to Node 5
4. Second Leaf!: Node 2 — Node 5 got the left box, explores right, hits 2 → Situation 2 → box [2], Return to Node 5
5. Merge at fork: Node 5 — left + right → [6] + [2] = [6, 2], Return big box up to Root 3
6. Right of Root: Node 1 — Root 3 explores right, hits 1 → Situation 2 → box [1], Return to Root 3
7. Finale: Node 3 — left + right → [6, 2] + [1] = [6, 2, 1]

5. Full Assembled Code

Glue the three pieces into LeetCode's Solution class — short, clean, logic transparent:

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:

        # DFS maze walker
        def get_leaves(node):
            # 1. Fall off the edge
            if not node:
                return []

            # 2. Dead end (Leaf Node)
            if not node.left and not node.right:
                return [node.val]

            # 3. Fork: left box + right box
            return get_leaves(node.left) + get_leaves(node.right)

        # Compare leaf boxes of both trees
        return get_leaves(root1) == get_leaves(root2)

6. Complexity

• Time Complexity: O(T₁ + T₂) where T is each tree's node count — DFS steps on every node exactly once
• Space Complexity: O(L₁ + L₂ + H) — L for the leaf Lists, H for the recursive Call Stack that remembers the walk-back path