【LeetCode】【剑指offer】【树的子结构】

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

     3
    / \
   4   5
  / \
 1   2
给定的树 B：

   4 
  /
 1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 

这道题和我们之前的判断子树的题非常相似，我们只需要修改一下之前的代码就能完成我们本道题的题解 

【LeetCode】【牛客】二叉树刷题_桜キャンドル淵的博客-CSDN博客

这篇博文的第六题我们微改一下就是我们这道题的结果

我们只需要将框起来的这部分改成下面的代码就能完成本道题的解答。

因为本道题需要判断的是只要有子树的结构就行，不一定要是子树。

也就是说下面这种情况可是可以的

 而不一定要是严格匹配到子树

 

所以在我们匹配的过程中子树的结点下面要是null，咱就返回TRUE，不用再继续匹配了，但如果是父树中的与子树匹配的结点为null，那就是FALSE。 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
//采用先序遍历的方式遍历我们的二叉树，然后对于每一个结点，我们都将判断
//以此结点为根节点的二叉树是否跟我们的子树相同
//注意，这里我们的返回时递归调用我们的左子树和右子树，并且以或的形式返回
//因为我们的左子树和右子树中，只要有一个中存在我们子树，整个递归的结果就应该是true
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (A==nullptr||B==nullptr)
        {
            return false;
        }
        if(isSameTree(A,B))
        {
            return true;
        }
        return isSubStructure(A->left,B)||isSubStructure(A->right,B);
    }
    bool isSameTree(struct TreeNode* p, struct TreeNode* q){
        if(p==nullptr&&q==nullptr)
        {
            return true;
        }
        if(p!=nullptr&&q==nullptr)
        {
            return true;
        }
        if(p==nullptr&&q!=nullptr)
        {
            return false;
        }
        if(p->val!=q->val)
        {
            return false;
        }
        return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    }
};