2021-05-10 LeetCode每日一题
链接：https://leetcode-cn.com/problems/leaf-similar-trees/
题目
请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
tree.png
举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
输入：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
输入：root1 = [1], root2 = [1]
输出：true
输入：root1 = [1], root2 = [2]
输出：false
输入：root1 = [1,2], root2 = [2,2]
输出：true
输入：root1 = [1,2,3], root2 = [1,3,2]
输出：false
给定的两棵树可能会有 1 到 200 个结点。
给定的两棵树上的值介于 0 到 200 之间。
分析
这题用BFS或者DFS都是可以的，只需要拿到叶子节点的值即可，至于怎么存储，因为题目只需要返回true or false，所以我这里选择使用String去存储叶子节点的值，然后直接判断两个字符串是否相等即可。不嫌麻烦也可以使用数组存。
BFS解法：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode 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) {
String s1 = getLeafValue(root1);
String s2 = getLeafValue(root2);
return s1.equals(s2);
}
private String getLeafValue(TreeNode root) {
StringBuffer sb = new StringBuffer();
// 双端队列
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int len = queue.size();
for (int i = 0; i < len; i++) {
TreeNode node = queue.poll();
// 叶子节点
if (node.left == null && node.right == null) {
sb.append(node.val).append(",");
continue;
}
// 右节点加入队列头
if (node.right != null) {
queue.offerFirst(node.right);
}
// 左节点加入队列头
if (node.left != null) {
queue.offerFirst(node.left);
}
}
}
return sb.toString();
}
}
时间复杂度O(m + n)，空间复杂度O(1)
image-20210510215300268.png
DFS解法：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode 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) {
StringBuffer sb1 = new StringBuffer();
StringBuffer sb2 = new StringBuffer();
dfs(root1, sb1);
dfs(root2, sb2);
return sb1.toString().equals(sb2.toString());
}
private void dfs(TreeNode root, StringBuffer sb) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
sb.append(root.val).append(",");
return;
}
dfs(root.left, sb);
dfs(root.right, sb);
}
}
时间复杂度O(m + n)，空间复杂度O(1)
image-20210510220258512.png
