LC 872. 叶子相似的树
题目描述
这是 LeetCode 上的 872. 叶子相似的树 ,难度为 简单。
请考虑一棵二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
举个例子,如上图所示,给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两棵二叉树的叶值序列是相同,那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的,则返回 true;否则返回 false 。
示例 1:
1 |
|
示例 2:1
2
3输入:root1 = [1], root2 = [1]
输出:true
示例 3:1
2
3输入:root1 = [1], root2 = [2]
输出:false
示例 4:1
2
3输入:root1 = [1,2], root2 = [2,2]
输出:true
示例 5:
1 |
|
提示:
- 给定的两棵树可能会有 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
23class Solution {
public boolean leafSimilar(TreeNode t1, TreeNode t2) {
List<Integer> l1 = new ArrayList<>(), l2 = new ArrayList<>();
dfs(t1, l1);
dfs(t2, l2);
if (l1.size() == l2.size()) {
for (int i = 0; i < l1.size(); i++) {
if (!l1.get(i).equals(l2.get(i))) return false;
}
return true;
}
return false;
}
void dfs(TreeNode root, List<Integer> list) {
if (root == null) return;
if (root.left == null && root.right == null) {
list.add(root.val);
return;
}
dfs(root.left, list);
dfs(root.right, list);
}
}
- 时间复杂度:
n
和m
分别代表两棵树的节点数量。复杂度为 $O(n + m)$ - 空间复杂度:
n
和m
分别代表两棵树的节点数量,当两棵树都只有一层的情况,所有的节点值都会被存储在 $list$ 中。复杂度为 $O(n + m)$
迭代
迭代其实就是使用「栈」来模拟递归过程,也属于树的遍历中的常见实现形式。
一般简单的面试中如果问到树的遍历,面试官都不会对「递归」解法感到满意,因此掌握「迭代/非递归」写法同样重要。
代码: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
26class Solution {
public boolean leafSimilar(TreeNode t1, TreeNode t2) {
List<Integer> l1 = new ArrayList<>(), l2 = new ArrayList<>();
process(t1, l1);
process(t2, l2);
if (l1.size() == l2.size()) {
for (int i = 0; i < l1.size(); i++) {
if (!l1.get(i).equals(l2.get(i))) return false;
}
return true;
}
return false;
}
void process(TreeNode root, List<Integer> list) {
Deque<TreeNode> d = new ArrayDeque<>();
while (root != null || !d.isEmpty()) {
while (root != null) {
d.addLast(root);
root = root.left;
}
root = d.pollLast();
if (root.left == null && root.right == null) list.add(root.val);
root = root.right;
}
}
}
- 时间复杂度:
n
和m
分别代表两棵树的节点数量。复杂度为 $O(n + m)$ - 空间复杂度:
n
和m
分别代表两棵树的节点数量,当两棵树都只有一层的情况,所有的节点值都会被存储在 $list$ 中。复杂度为 $O(n + m)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.872
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!