[数据结构与算法]leetcode 572. 另一棵树的子树

题目

题解

递归
官方题解还用到了kmp和哈希的。。。。这里我就没看了

2021.12.7

这题的递归，我有点没弄明白，后来看了题解才忽略了，两个二叉树完全相等的情况。。。。

class Solution {
public:
    bool check(TreeNode*root,TreeNode*subRoot) //判断是否是一个相同的树
    {
        //递归结束条件一：当其左右子树为空 代表已经匹配上
        if(root ==nullptr&&subRoot == nullptr)return true;
        //递归结束条件二：倘若有一个子树不为空 代表未匹配上
        if(!root||!subRoot)return false;
        //递归结束条件三 若节点值不同 代表未匹配上
        if(root->val != subRoot->val) return false;  
        //若为相同一个树 则两棵树的左右子树是相同的 同步移动两棵树的指针
    return check(root->left,subRoot->left)&&check(root->right,subRoot->right);
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        //若subRoot为空树 怎么比较都是true
        //if(subRoot == nullptr)return true;
        //若root为空树，怎么比较都是false
        if(root == nullptr)return false;
        //符合subRoot是root子树的三个条件：两棵树完全相同；SubRoot为root的左子树，SubRoot为root的右子树
   return check(root,subRoot)||isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
    }
};