题解 | #树的子结构#

题目难度：较难
考察知识：树，递归
题目大意：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

1.问题分析
首先考虑如何判断B是A的子结构，在A的遍历过程中出现了B即说明B是A的子结构，需要注意题目说明了空树不是任意一棵树的子结构，先不考虑空树，想要确实B是否是A的子结构应该如何判断，当A的某子树treeA的value和B的value相同并且和的左右子树也是treeA的左右子树的子结构，这时可以判断B是A的子结构，否则判断B是否是A的左右子树的子结构，如图

具体做法为

算法设计
从上面的分析可以发现，涉及了很多调用子树的情况，所以使用递归可以很方便的处理子树问题
但是要注意的是题目限制了空树不是任意树的子结构！！！
需要特判B是否为空，否则会发生错误，原因是上述判断B是A的子结构的递归终止条件是B的子树为空
所以不加判断一定会得到错误答案
下面给出代码

class Solution {
public:
    int f=0;//特判
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(!f)
        {
            f=1;
            //将f变为1，这是为了递归时不需要特判
            if(pRoot2==nullptr)return 0;
            //如果B是空直接返回false
        }
        if(pRoot1==nullptr&&pRoot2==nullptr)return 1;
        //ab同时为空说明也可能存在子结构关系，所以要放到最前面判断
        if(pRoot1==nullptr)return 0;
        //a为空说明a遍历完了也没找到b
        if(pRoot2==nullptr)return 1;
        //b子树为空说明子树是a的子结构
       if(pRoot1->val==pRoot2->val&&HasSubtree(pRoot1->left,pRoot2->left)&&HasSubtree(pRoot1->right, pRoot2->right))
           return 1;//如果当前value相同并且左右子树也相同，说明已经存在了子结构关系，返回1
            if(HasSubtree(pRoot1->left,pRoot2))return 1;//b是a左子树的子结构，返回1
            if(HasSubtree(pRoot1->right, pRoot2))return 1;//b是a右子树的子结构，返回1
            return 0;//都不是返回0
    }
};

可以发现，关于树的题大多可以递归处理，并且思路清晰，代码简洁，但递归本身并不是很好理解，并且要考虑清楚递归的终止条件是什么