Leetcode l872. 叶子相似的 做题小结

题目:

请考虑一棵二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

举个例子,如上图所示,给定一棵叶值序列为 (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], root2 = [1]
输出:true
示例 3:

输入:root1 = [1], root2 = [2]
输出:false
示例 4:

输入:root1 = [1,2], root2 = [2,2]
输出:true
示例 5:

输入:root1 = [1,2,3], root2 = [1,3,2]
输出:false

提示:

给定的两棵树可能会有 1 到 200 个结点。
给定的两棵树上的值介于 0 到 200 之间。

解题思路:

思路和算法

首先,让我们找出给定的两个树的叶值序列。之后,我们可以比较它们,看看它们是否相等。

要找出树的叶值序列,我们可以使用深度优先搜索。如果结点是叶子,那么 dfs 函数会写入结点的值,然后递归地探索每个子结点。这可以保证按从左到右的顺序访问每片叶子,因为在右孩子结点之前完全探索了左孩子结点。

代码:

class Solution {    public boolean leafSimilar(TreeNode root1, TreeNode root2) {        List<Integer> leaves1 = new ArrayList();        List<Integer> leaves2 = new ArrayList();        dfs(root1, leaves1);        dfs(root2, leaves2);        return leaves1.equals(leaves2);    }    public void dfs(TreeNode node, List<Integer> leafValues) {        if (node != null) {            if (node.left == null && node.right == null)                leafValues.add(node.val);            dfs(node.left, leafValues);            dfs(node.right, leafValues);        }    }}

来源:https://www.icode9.com/content-4-784051.html

(0)

相关推荐

  • (1条消息) 万字长文!二叉树入门和刷题看这篇就够了!

    今天是小浩算法 "365刷题计划" 二叉树入门 - 整合篇.本篇作为入门整合篇,已经砍去难度较大的知识点,所有列出的内容,均为必须掌握.因为很长,写下目录: 二叉树是啥 二叉树的最 ...

  • 大舍得:寒门做题家的身上,到底存在什么致命缺陷?

    无教养,无以立人. Manners-maketh-man. 正文: 对于关注灏泽的为人父母者,我想说句真心话,那就是从我手里审阅过运势命格孩子数不胜数,其实很多孩子需要的仅仅是适度是引导,就能成长得很 ...

  • 【高中数学】了解这50个二级结论,提升做题速度,成绩大飞跃!

    经常有家长反映:"我的孩子数学学习成绩中上等,本来可达到班级前几名的.但是几乎每次数学考试都会因为粗心而丢分,丢分的题目都是简单的选择和填空题,老师,这种情况到底应该怎么办呢?" ...

  • 中考数学备考:中考数学做题技巧及方法

    有些同学天天趴在那里做题,但解出的题量多,花的时间却很多.这到底是什么原因呢?其中的原因之一,就是解题速度太慢.详细中考数学做题技巧如下: 中考数学做题技巧 一.熟悉习题中所涉及的内容,包括定义.公式 ...

  • 代用票实做题(一)

    一.2016年8月5日,由襄樊开往华山的T123次新空列车(经由安康.西安),安康开车后一旅客持8月6日襄樊至安康1331次列车硬座车票,携带1名身高1.5米的儿童,要求办理一张卧铺到太原,宿营车21 ...

  • 【打卡做题】河道来沙系数是个什么鬼

    青岛二模刚刚结束, 先上一组试试火, 就问你晕不晕    有点烧脑 不服来战 答案:1.B2.B3.BD 解析: 1.B 由材料可知,河道来沙系数主要反映河道输沙能力与水沙变化关系,由图可知,夏季来沙 ...

  • 【打卡做题】锡矿出露何处寻?

    青岛二模刚刚结束, 再来一组看看, 好像更烧脑, (2021年青岛二模)九嶷山地区位于湘南地区,是我国重要的锡成矿区之一,区内构造经历了多期构造活动,不同走向断裂不仅反映了断裂构造的时空演化关系,而且 ...

  • 苦做题不如乐学习

    [光明谈] 教育部近日对中小学作业管理提出"十条要求",其中要求小学一.二年级不布置书面家庭作业,小学其他年级每天书面作业完成时间应以一小时为限. 要求精细,概因中小学生课外课业压 ...

  • 高考冲刺丨50个公式,50种快速做题方法!赶快来看!!

    专业的高中数学学习平台 每天17:00不见不散 今天,为大家整理了高中数学50个快速解题的公式,一定要记住! 1 . 适用条件 [直线过焦点],必有ecosA=(x-1)/(x+1),其中A为直线与焦 ...

  • 做题速度吗?试卷答不完?这份理综答题技巧送给慢慢的你

    答题顺序 物理 物理审题要点 1.审题要仔细,关键字眼不可疏忽 审题时一定要仔细,尤其要注意一些重要的关键字眼,不要以为是'容易题''陈题'就一眼带过,要注意'陈题'中可能有'新意'.也不要一眼看上去 ...