leetcode872. 叶子相似的树(java)

这篇具有很好参考价值的文章主要介绍了leetcode872. 叶子相似的树(java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

难度 - 简单
leetcode - 872. 叶子相似的树

请考虑一棵二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
leetcode872. 叶子相似的树(java),java,数据结构,算法,java,开发语言,算法,数据结构,贪心算法举个例子,如上图所示,给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两棵二叉树的叶值序列是相同,那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的,则返回 true;否则返回 false 。

示例1:
leetcode872. 叶子相似的树(java),java,数据结构,算法,java,开发语言,算法,数据结构,贪心算法
输入: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:
leetcode872. 叶子相似的树(java),java,数据结构,算法,java,开发语言,算法,数据结构,贪心算法输入:root1 = [1,2,3], root2 = [1,3,2]
输出:false

提示:
给定的两棵树结点数在 [1, 200] 范围内
给定的两棵树上的值在 [0, 200] 范围内

leetcode872. 叶子相似的树(java),java,数据结构,算法,java,开发语言,算法,数据结构,贪心算法

递归

我们可以使用深度优先搜索的方法得到一棵树的「叶值序列」。
具体地,在深度优先搜索的过程中,我们总是先搜索当前节点的左子节点,再搜索当前节点的右子节点。如果我们搜索到一个叶节点,就将它的值放入序列中。
在得到了两棵树分别的「叶值序列」后,我们比较它们是否相等即可。

代码演示:文章来源地址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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五)

      目录 一,单值二叉树 题目详情: 解法:父子比较法 解题思路: 思路实现: 源代码: 二,相同的树 题目详情: 解法:比较法 解题思路: 思路实现: 源代码: 三,翻转二叉树 解法:替换法 解题思路: 思路实现: 源代码: 题目详情: 如果 二叉树 每个节点都具有 相

    2024年02月07日
    浏览(68)
  • 【数据结构】(二叉树)计算结点|叶子结点|高度|第K层结点数

      目录 概念: 特殊的二叉树 二叉树的性质 二叉树的存储结构 二叉树的创建 二叉树遍历  前序: 中序: 后序:  计算结点数 计算叶子结点数 计算树的高度(深度) 计算第K层结点数   一颗二叉树是结点的一个有限集合,该集合: 1.或者为空; 2.由一个根节点加上两棵别称

    2024年02月03日
    浏览(38)
  • 【数据结构】二叉树的节点总个数、叶子节点个数、第K层节点个数、二叉树的深度

    目录 1.结点总个数 1.1 局部静态变量法 思维 代码 不足之处 2.传指针法 程序代码 3.递归法 思想 程序代码 详细过程 2.叶子节点个数 思想 程序代码 3.第K层节点个数 思想 程序代码 4.二叉树深度 思想 程序代码         求二叉树节点总个数、叶子节点个数、第k层节点个数、二叉

    2024年02月02日
    浏览(40)
  • 14-数据结构-二叉树的创建以及前中后遍历,以及结点和叶子节点的计算(C语言)

    概述:         二叉树,这里采用孩子链表存储法,即一个数据域和两个左右孩子指针域。随后递归进行遍历即可。在创建二叉树的时候,先创建各个二叉树结点(这里的结点采用动态分配,因此结点为指针变量),随后,再根据逻辑结构图,手动通过左右指针域,链接到对

    2024年02月11日
    浏览(45)
  • java数据结构与算法刷题-----LeetCode283. 移动零

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 双指针,用right和left两个指针,将非0元素,全部按顺序换到数组前面。left指向左边非0元素应该插入的位置,right找到非

    2024年01月21日
    浏览(49)
  • java数据结构与算法刷题-----LeetCode566. 重塑矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 代码:时间复杂度O(r*c).除题目要求外,算法本身没有需要额外空间,空间复杂度O(1) 从0开始算,一个3列n行矩阵中,每行就有3个元

    2024年01月21日
    浏览(46)
  • java数据结构(哈希表—HashMap)含LeetCode例题讲解

      目录 1、HashMap的基本方法 1.1、基础方法(增删改查) 1.2、其他方法  2、HashMap的相关例题 2.1、题目介绍 2.2、解题 2.2.1、解题思路 2.2.2、解题图解 2.3、解题代码 HashMap 是一个散列表,它存储的内容是键值(key-value)映射。 HashMap 的 key 与 value 类型可以相同也可以不同,根据定

    2024年02月05日
    浏览(52)
  • java数据结构与算法刷题-----LeetCode287. 寻找重复数

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 弗洛伊德判圈法,也就是快慢指针判圈法(龟兔赛跑算法),此算法分为两个步骤 判断是否有环,并得到快慢指针相遇

    2024年01月24日
    浏览(43)
  • java数据结构与算法刷题-----LeetCode766. 托普利茨矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 这道题只要换一种理解方式,瞬间就会变的很简单。 题目描述是每个元素左上和右下对角线元素都相同。但是,我们发

    2024年01月25日
    浏览(48)
  • java数据结构与算法刷题-----LeetCode667. 优美的排列 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 题目要求我们返回一个数组长度为n的数组,必须含有1~n的所有数,并且从左到右,相邻的元素依次相减,它们的差,必

    2024年01月25日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包