题目描述
难度 - 简单
leetcode - 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] 范围内
递归
我们可以使用深度优先搜索的方法得到一棵树的「叶值序列」。
具体地,在深度优先搜索的过程中,我们总是先搜索当前节点的左子节点,再搜索当前节点的右子节点。如果我们搜索到一个叶节点,就将它的值放入序列中。
在得到了两棵树分别的「叶值序列」后,我们比较它们是否相等即可。文章来源:https://www.toymoban.com/news/detail-705425.html
代码演示:文章来源地址https://www.toymoban.com/news/detail-705425.html
/**
* 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 static boolean leafSimilar(TreeNode root1, TreeNode root2) {
ArrayList<Integer> s1 = new ArrayList<>();
ArrayList<Integer> s2 = new ArrayList<>();
dfs(root1,s1);
dfs(root2,s2);
return s1.equals(s2);
}
static void dfs(TreeNode root,List<Integer> s1){
if(root == null){
return;
}
if(root.left == null && root.right == null){
s1.add(root.val);
return;
}
dfs(root.left,s1);
dfs(root.right,s1);
}
}
到了这里,关于leetcode872. 叶子相似的树(java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!