⚡Flashcard Drill➔
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.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems

中文速览与面试要点

叶子相似的树

请考虑一棵二叉树上所有的叶子,这些叶子的值按 从左到右 的顺序排列形成一个 叶值序列 。举个例子,如上图所示,给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。如果有两棵二叉树的叶值序列是相同,那么我们就认为它们是 叶相似 的。如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的,则返回 true;否则返回 false。约束:给定的两棵树结点数在 [1, 200] 范围内;0 ≤ Node.val ≤ 200。

核心要点

  • DFS 收集叶子序列(标准解) :分别对两棵树做 DFS,按从左到右的顺序收集叶子节点的值,然后比较两个序列是否相等。
  • 「叶子」的定义 :左右子节点都为空的节点。
  • 复杂度 :O(m + n) 时间、O(m + n) 空间。
  • 优化 :可以用生成器惰性产出叶子值,逐个比较而不存储完整序列,空间 O(h)。

常见陷阱

  • 把「非叶子节点」的值也加入序列 :必须先判断「左右子节点都为空」才是叶子。
  • 只比较序列长度 :必须逐元素比较。
  • 用 BFS 收集 :层序遍历的顺序不是「从左到右的叶子顺序」。必须用 DFS(先左后右)。
  • 递归深度 :n ≤ 200,安全。

参考实现

class Solution:
    def leafSimilar(self, root1: 'TreeNode', root2: 'TreeNode') -> bool:
        def leaves(node, out):
            if not node:
                return
            if not node.left and not node.right:
                out.append(node.val)
                return
            leaves(node.left, out)
            leaves(node.right, out)

        a, b = [], []
        leaves(root1, a)
        leaves(root2, b)
        return a == b