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/

发表评论

电子邮件地址不会被公开。