LeetCode 题解工作台
叶子相似的树
请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。 举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。 如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。 如果给定的两个根结点分别为 root1 和 root2 的树是…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 二分·树·traversal
答案摘要
我们可以使用深度优先搜索来遍历两棵树的叶子节点，分别将叶子节点的值存储在两个列表 和 中，最后比较两个列表是否相等。 时间复杂度 ，空间复杂度 。其中 为树的节点数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
示例 1：
输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8] 输出：true
示例 2：
输入：root1 = [1,2,3], root2 = [1,3,2] 输出：false
提示：
- 给定的两棵树结点数在
[1, 200]范围内 - 给定的两棵树上的值在
[0, 200]范围内
解题思路
方法一：DFS
我们可以使用深度优先搜索来遍历两棵树的叶子节点，分别将叶子节点的值存储在两个列表 和 中，最后比较两个列表是否相等。
时间复杂度 ，空间复杂度 。其中 为树的节点数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
def dfs(root: Optional[TreeNode], nums: List[int]) -> None:
if root.left == root.right:
nums.append(root.val)
return
if root.left:
dfs(root.left, nums)
if root.right:
dfs(root.right, nums)
l1, l2 = [], []
dfs(root1, l1)
dfs(root2, l2)
return l1 == l2
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N + M) |
| 空间 | O(N + M) |
面试官常问的追问
外企场景- question_mark
Asks about leaf order preservation in DFS traversal.
- question_mark
Checks if candidate handles trees of different shapes with identical leaf sequences.
- question_mark
Probes for optimization beyond naïve full-tree comparison.
常见陷阱
外企场景- error
Ignoring the left-to-right order of leaves leading to incorrect sequence comparison.
- error
Mistaking internal nodes for leaves during sequence collection.
- error
Assuming trees of different structures cannot be leaf-similar.
进阶变体
外企场景- arrow_right_alt
Compare leaf sequences using iterative DFS instead of recursion.
- arrow_right_alt
Handle N-ary trees or trees with more than two children per node.
- arrow_right_alt
Return the matching leaf sequence if trees are leaf-similar instead of a boolean.