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
- Collect the leaf values of each tree with a DFS that visits the left child first.
- Compare the two sequences.
- The left-first order is essential, since the sequence is defined left to right.
- 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.
🧩 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