leetcode572-另一个树的子树

原题

给定两个非空二叉树 st,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 1:
给定的树 s:

     3
    / \
   4   5
  / \
 1   2

给定的树 t:

   4 
  / \
 1   2

返回 true,因为 t 与 s 的一个子树拥有相同的结构和节点值。

示例 2:
给定的树 s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

给定的树 t:

   4
  / \
 1   2

返回 false。

解法

思想

参考leetcode100-相同的树的做法,递归判断t和s中的子树是否相同。

代码

class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return false;  
        return t == null || isSubtree(s.left, t) || isSubtree(s.right, t) || isSameTree(s,t);
    }

    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));
    }
}

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

(0)
彭晨涛彭晨涛管理者
上一篇 2020年5月7日
下一篇 2020年5月8日

相关推荐

  • leetcode350-两个数组的交集II

    原题 给定两个数组,编写一个函数来计算它们的交集。 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 示例2: 输入: nums1 = …

    算法 2019年12月23日
    0410
  • leetcode11-盛最多水的容器

    原题 给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i,…

    2020年2月27日
    0250
  • leetcode54-螺旋矩阵

    原题 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。 示例 1: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6…

    算法 2019年11月15日
    0100
  • leetcode559-N叉树的最大深度

    原题 给定一个 N 叉树,找到其最大深度。 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 例如,给定一个 3叉树 : 我们应返回其最大深度,3。 说明: 树的深度不会…

    2020年1月20日
    090
  • leetcode994-腐烂的橘子

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

    2020年3月4日
    0100
  • leetcode108-将有序数组转换为二叉搜索树

    原题 将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定有序数…

    算法 2020年1月18日
    090
  • 使用递归函数逆序一个栈

    原题(来源:牛客网) 一个栈依次压入1,2,3,4,5那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后,从栈顶到栈底为1,2,3,4,5,也就是实现了栈中元素的逆序,请设计…

    算法 2020年4月19日
    0250
  • leetcode498-对角线遍历

    这是一个Z字形编排问题,JEPG的编码过程中也会用到。 原题 给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下…

    2019年11月14日
    0110
  • leetcode235-二叉搜索树的最近公共祖先

    原题 给定一个二叉二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x …

    2020年1月17日
    0100
  • leetcode999-车的可用捕获量

    原题 999. 车的可用捕获量 - 力扣(LeetCode) 解法 思想 这道题题目有点难理解,其实就是上下左右搜索,质量有点低了。 代码 class Solution { cha…

    算法 2020年3月26日
    070

发表回复

登录后才能评论