572. 另一个树的子树(递归)

阳光穿透心脏的1/2处 2023-10-05 04:22 47阅读 0赞

#### 572. 另一个树的子树 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]

## 解题思路 ##

PS:这题没太抓住细节，日后再看一下官方题解

该题还是遵循“找到一个节点该做的事情，剩下的交给递归框架”。

归很重要的一点就是找到最简单的子问题。我们可以设想一下，一棵树s就三个节点，root、left、right。我们要做的就是找到首先以root为根节点的子树，看他是否在t中有相同结构，再就是找到以left为根节点…right也是同理…。

所以我们就构造一个辅助函数去对比，两颗子树的结构是不是相同。要注意的是假如现在是以root为根节点嘛。我们比较的时候应该比较的是一颗完整的子树结构，即 这颗s的子树应该是`[root,left,right]`这才叫一颗完整的子树。再比如现在以left为根节点，那么现在完整的子树应该为`[left,left.left,left.right]`。

这三个都要比较，只有这三个都能在t中对应起来，才能说s中有一颗完整的子树在t中存在相同结构的子树。

## 代码 ##

class Solution {
        
        public boolean isSubtree(TreeNode s, TreeNode t) {
        
    
        if (t == null) return true;   // t 为 null 一定都是 true:空树为任何树的子树
        if (s == null) return false;  // 这里 t 一定不为 null, 只要 s 为 null，肯定是 false
    
    
    
            boolean rootFlag=help(s,t);//s也是s的子树，看s这颗子树是否在t中有相同结构的子树
    
    
            boolean leftFlag=isSubtree(s.left,t);
            boolean rightFlag=isSubtree(s.right,t);
    
        return leftFlag || rightFlag||rootFlag;//只要s这一整棵树中， 有一种子树在t中有相同结构的子树，就应该返回true。
        }
    
    
        public boolean help(TreeNode s, TreeNode t){
        //判断两棵树是否相同
            //base case
           if (s == null && t == null) return true;
            if (s == null || t == null) return false;
    
            //一个节点要做的事情
            if (s.val != t.val) return false;
    
            boolean leftFlag=help(s.left,t.left);
            boolean rightFlag=help(s.right,t.right);
    
            return  leftFlag&&rightFlag;//因为是要求“具有相同结构和节点值”，所以必须要左子树返回的值为true，右子树返回的值也为true，即该节点，该节点的左子树，该节点的右子树（他们仨合起来称成为了一颗完整的s的子树），都可以在t中找到相同结构的子树。
            
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201224002835811.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201224002842771.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70