leetcode100-相同的树

原题

给定两个二叉树,编写一个函数来检验它们是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:

输入:      1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true

示例 2:

输入:     1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false

示例 3:

输入:      1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

解法

思想

递归判断吧,两个树相同的条件是,左子树相同且右子树相同且根节点的值相等;或者两个根节点都是null。

代码

一行代码极简风格

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return (p==null && q==null) || (q!=null && p!= null && p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right));
    }
}

拆分出来的条件是:
(p==null && q==null):两个根节点都为null,或者

(q!=null && p!= null && p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right)):两个根节点都不为null,且各自对应的左右子树相同。

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode100-%e7%9b%b8%e5%90%8c%e7%9a%84%e6%a0%91/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年5月6日 22:44
下一篇 2020年5月8日

相关推荐

  • leetcode590-N叉树的后序遍历

    原题 给定一个 N 叉树,返回其节点值的后序遍历。 例如,给定一个 3叉树 : 返回其前序遍历: [5,6,3,2,4,1]. 说明: 递归法很简单,你可以使用迭代法完成此题吗? …

    2020年1月20日
    080
  • leetcode110-平衡二叉树

    原题 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1:  给定二叉树 […

    算法 2020年1月17日
    0170
  • leetcode33-搜索旋转排序数组

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值,…

    算法 2020年1月1日
    0150
  • leetcode145-二叉树的后序遍历

    原题 给定一个二叉树,返回它的 后序 遍历。 示例: 输入: [1,null,2,3]  1   \    2 &nbs…

    算法 2020年1月10日
    070
  • leetcode994-腐烂的橘子

    原题 在给定的网格中,每个单元格可以有以下三个值之一: 值 0 代表空单元格;值 1 代表新鲜橘子;值 2 代表腐烂的橘子。每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜…

    2020年3月4日
    0100
  • leetcode322-零钱兑换

    原题 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。 示例 1…

    算法 2020年3月8日
    0130
  • leetcode530-二叉搜索树的最小绝对差

    原题 给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。 示例: 输入:    1    &n…

    算法 2020年2月22日
    01320
  • leetcode136-只出现一次的数字

    原题 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明: 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗…

    算法 2019年12月18日
    0130
  • leetcode435-无重叠区间

    原题 给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没…

    算法 2020年2月18日
    02410
  • leetcode15-三数之和

    原题 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。 注意:…

    算法 2020年5月4日
    0150

发表回复

登录后才能评论