友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
872. 叶子相似的树
请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列。
举个例子，如上图所示，给定一棵叶值序列为 (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]范围内
思路分析
最优解是深度优先遍历，我用的是迭代法。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-08-18 21:33:57
*/
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
List<TreeNode> first = getLeaves(root1);
List<TreeNode> second = getLeaves(root2);
if (first.size() != second.size()) {
return false;
}
for (int i = 0; i < first.size(); i++) {
if (first.get(i).val != second.get(i).val) {
return false;
}
}
return true;
}
private List<TreeNode> getLeaves(TreeNode root) {
if (Objects.isNull(root)) {
return new ArrayList<>();
}
List<TreeNode> result = new LinkedList<>(List.of(root));
boolean hasNext = true;
while (hasNext) {
hasNext = false;
List<TreeNode> next = new ArrayList<>();
while (!result.isEmpty()) {
TreeNode node = result.removeFirst();
if (Objects.isNull(node.left) && Objects.isNull(node.right)) {
next.add(node);
} else {
if (Objects.nonNull(node.left)) {
next.add(node.left);
}
if (Objects.nonNull(node.right)) {
next.add(node.right);
}
hasNext = true;
}
}
result = next;
}
return result;
}