叶子相似的树 图解题解
这道题到底在问什么
- 输入
- root1 叶序列 [60,70,80]、root2 叶序列 [60,70,80]
- 输出
- true
- 输入
- root1 叶序列 [20,30]、root2 叶序列 [30,20]
- 输出
- false(顺序不同)
最优解：一步一步想明白
- 3记住「DFS 先左后右收叶子 → 两序列比一比」,下面逐帧套它。关键是收集顺序必须是从左到右,所以递归先走左子树。
- 4DFS 走到节点 30,它还有孩子,不是叶子,先往左子树深入。
- 5DFS 走到节点 50,它还有孩子,不是叶子,先往左子树深入。
- 6走到节点 60,它左右孩子都空,是叶子。把 60 追加进 左树 的叶序列。
- 7左树 的叶序列又长一个:现在是 [60](绿色是刚收进来的 60)。
- 8走到节点 70,它左右孩子都空,是叶子。把 70 追加进 左树 的叶序列。
- 9左树 的叶序列又长一个:现在是 [60、70](绿色是刚收进来的 70)。
- 10DFS 走到节点 10,它不是叶子;左子树是空的,转到右孩子 80 继续。
- 11走到节点 80,它左右孩子都空,是叶子。把 80 追加进 左树 的叶序列。
- 12左树 的叶序列又长一个:现在是 [60、70、80](绿色是刚收进来的 80)。
- 13左树 整棵 DFS 走完,从左到右的叶序列定下来:[60、70、80](绿色三个叶子)。
- 14DFS 走到节点 90,它还有孩子,不是叶子,先往左子树深入。
- 15走到节点 60,它左右孩子都空,是叶子。把 60 追加进 右树 的叶序列。
- 16右树 的叶序列又长一个:现在是 [60](绿色是刚收进来的 60)。
- 17DFS 走到节点 40,它还有孩子,不是叶子,先往左子树深入。
- 18走到节点 70,它左右孩子都空,是叶子。把 70 追加进 右树 的叶序列。
- 19右树 的叶序列又长一个:现在是 [60、70](绿色是刚收进来的 70)。
- 20走到节点 80,它左右孩子都空,是叶子。把 80 追加进 右树 的叶序列。
- 21右树 的叶序列又长一个:现在是 [60、70、80](绿色是刚收进来的 80)。
- 22右树 整棵 DFS 走完,从左到右的叶序列定下来:[60、70、80](绿色三个叶子)。
- 23逐位比对两棵树的叶序列。第 1 位:左树是 60、右树是 60,相等,继续看下一位。
- 24逐位比对两棵树的叶序列。第 2 位:左树是 70、右树是 70,相等,继续看下一位。
- 25逐位比对两棵树的叶序列。第 3 位:左树是 80、右树是 80,相等,继续看下一位。
- 26两棵树的叶序列 [60、70、80] 和 [60、70、80] 逐位都相等,所以两棵树叶子相似,返回 true。回头看,我们没有去比树的形状,只把各自的叶子从左到右拉成一条序列再比,形状再不同也不影响。
⚠️ 容易写错的地方
✗ 错：收集顺序左右搞反
✓ 对：DFS 必须先递归左、再递归右
题目要的是「从左到右」的叶序列,先右后左收出来顺序就反了,会误判
✗ 错：把「值相同」当「相似」
✓ 对：要序列逐位且按顺序都相等
叶子集合相同但顺序不同也不算相似,如 [20,30] 与 [30,20]
✗ 错：叶子判定写成只看一个孩子
✓ 对：叶子是左孩子和右孩子都为空
只有一个孩子的节点不是叶子,不能收它的值
完整代码（Python / C++ / Java）
Python
from typing import List, Optional
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 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 == bC++
#include <algorithm>
#include <functional>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode():val(0),left(nullptr),right(nullptr){} TreeNode(int x):val(x),left(nullptr),right(nullptr){} TreeNode(int x,TreeNode*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: bool leafSimilar(TreeNode* root1,TreeNode* root2){ vector<int>a,b; function<void(TreeNode*,vector<int>&)> dfs=[&](TreeNode*n,vector<int>&v){ if(!n)return; if(!n->left&&!n->right)v.push_back(n->val); dfs(n->left,v); dfs(n->right,v);}; dfs(root1,a); dfs(root2,b); return a==b; }};Java
import java.util.*;
class TreeNode{int val;TreeNode left,right;TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val,TreeNode left,TreeNode right){this.val=val;this.left=left;this.right=right;}}
class Solution{ public boolean leafSimilar(TreeNode root1,TreeNode root2){ ArrayList<Integer>a=new ArrayList<>(),b=new ArrayList<>(); dfs(root1,a); dfs(root2,b); return a.equals(b);} void dfs(TreeNode n,List<Integer>v){ if(n==null)return; if(n.left==null&&n.right==null)v.add(n.val); dfs(n.left,v); dfs(n.right,v);} }复杂度
时间
O(n1 + n2)
两棵树各遍历一次,n1、n2 是两树节点数;最后比较序列是叶子个数级,不超过 O(n)
空间
O(h1 + h2 + L1 + L2)
递归栈深度等于两树高 h1、h2,外加显式保存的两条叶序列 L1、L2(叶子数);最坏树退化成链、叶子也多时可到 O(n1 + n2)。若想压到 O(h1+h2),得改成同步生成两树叶子、边走边比
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 叶子相似的树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能边 DFS 边比较、省掉存整条序列?+
可以,但要小心。一种做法是用迭代(显式栈)分别对两棵树做 DFS,各自只「按需吐出下一个叶子」,两边同步取下一个叶子比较,一旦不等就提前返回 false,这样空间从 O(叶子数) 降到 O(树高);代价是两个遍历要交替推进、写起来更绕。面试里能说出「同步生成 + 逐个比 + 提前退出」就到位。
为什么用 DFS 而不是 BFS 来收叶子?+
BFS 是按层收集,叶子会按「层」而不是按「从左到右」吐出来,顺序不对。要拿到从左到右的叶序列,自然用先左后右的 DFS;当然也能用 BFS 但需要额外按位置排序,不如 DFS 直接。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 叶子相似的树 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。