刷题——一棵树是另一棵树的子树

文章目录

题目描述：

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

题目分析：

本题用到了递归的方法，这就需要有宏观观察思考问题。

首先，通过读题，我们知道，subRoot 是 root 树的一颗子树，因此，我们可以有以下的思路，将一颗子树单独看做一个整体，同样的也是一颗树，所以，我们可以定义一个判断两棵树是否相同的方法，用于判断两棵树相等的情况。

其次，当我们有了实现判断两棵树相同的方法的思路后，我们需要思考，要判断 root 和 subRoot 的相同需要有那几个方向。

1.当 root 的根与 subRoot 的根相同的情况。

2.当 root 的左子树与 subRoot 的根相同的情况

3.当 root 的右子树与 subRoot 的根相同的情况

代码实现

class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null || subRoot == null){return false;}//1.用于判断两棵树是否相同if(isSametree(root,subRoot)){return true;}//2.判断左树是否存在相同if(isSubtree(root.left,subRoot)){return true;}//3.判断右树是否存在相同if(isSubtree(root.right,subRoot)){return true;}//上述比较无法通过时表明不存在相同部分return false;}public boolean isSametree(TreeNode p,TreeNode q){//检查树是否相等//1.当p，q所指向的值同时为null时表明此时这侧的树相同if(p == null && q == null){return true;}//2.当p，q所指向的值不同时为null时表明树不同if(p == null || q == null){return false;}//3.当p，q所指向的值不同时，表明树不同if(p.val != q.val){return false;}//对左右同时进行判断return (isSametree(p.left,q.left) && isSametree(p.right,q.right));}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！