题解 | #树的子结构#

这题的基本思路很简单，难在对于情况的判断。
上来看题首先确定题目中要遍历二叉树，并且还需要一个方法来判断是否有相同的结构。注意，这里判断的逻辑与判断两树是否相同基本类似。处理起来就是通过遍历原始树的结点，对每一个结点都调用判断结构的方法，若找到一个结点返回true，则直接返回true。
这里说一下判断两个结点是否是相同结构的逻辑，首先若两结点相同，则继续判断其左右结点是否相同，依次重复，直到遍历完给出的子逻辑，返回true，若途中遇到一个结点不同，或原始树先于给出的子结构为空，则返回false。
这里的结束判断逻辑有点小坑，想不明白的话容易出错。最开始以为子结构只要出现就会与原始树中直到叶子结点都完全相同。回顾题中例子后发现子结构只需是原始树中的一部分即可，并不需要包含完整的叶子结点。
树的递归方面选择了先序遍历，比较基础。

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    bool result = false;
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(!pRoot1 || !pRoot2){
            return false;
        }
        if(isEqual(pRoot1, pRoot2)){
            return true;
        }
        go(pRoot1->left, pRoot2);
        go(pRoot1->right, pRoot2);
        return result;
    }
    void go(TreeNode* p, TreeNode *pRoot2){
        if(!p){
            return ;
        }
        if(isEqual(p, pRoot2)){
            result = true;
        }
        go(p->left, pRoot2);
        go(p->right, pRoot2);
    }
    bool isEqual(TreeNode* p1, TreeNode* p2){
        if(!p2 || (!p2->left && p2->right && p2->right == p1 ->right) || (!p2->right && p2->left && p2->left == p1->left)){
            return true;
        }
        if((!p1&&p2) || p1->val != p2->val){
            return false;
        }
        return isEqual(p1->left, p2->left) && isEqual(p1->right, p2->right);
    }
};