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

572. 另一个树的子树

• 题目
• 解题思路
• 代码

题目

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

解题思路

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中找到相同结构的子树。
        
    }
}