题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

 

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
//网络来源的代码
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
           if(!pRoot1 || !pRoot2) return false;
            //遍历节点，找到 pRoot1 == pRoot2 的节点
           return check(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2); 
    }
    
   bool check(TreeNode* A, TreeNode* B){
       if (!B) return true;//A不空B空-B为A的子树 或 A空B空-相同，都返回true
       if (A && B){//A B存在验证val值
           if((A->val == B->val) )
           return check(A->left, B->left) && check(A->right, B->right);
       }
       return false;
   }
    
};