题解 | #树的子结构#

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
	/*
		双树判断，双迭代解决
		第一层迭代是否存在子树
		第二层迭代，子树中的特征判断
	*/
	bool judge(TreeNode* pRoot1, TreeNode* pRoot2)		// 第二层迭代
	{
		bool left = true, right = true;			// 一开始假设两者的左右子节点都是相等的
		if(!pRoot1 || pRoot1->val != pRoot2->val){	// 树结构的节点为空或者两者值不等，都是认为非子结构的
			// std::cout << pRoot1->val << " " << pRoot2->val << std::endl;
			return false;
		}
		// 以待判断的树左右节点为条件判断左右子节点与树的子节点关系
		if(pRoot2->left)	
			left = judge(pRoot1->left, pRoot2->left);
		if(pRoot2->right)
			right = judge(pRoot1->right, pRoot2->right);
		if(left&&right)
			return true;	// 两个子节点都是相等的话，那么认为是子结构
		else 
			return false;
	}


    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {	// 第一层迭代，判断是否在下一节点中开始子树判断
		if(!pRoot2||!pRoot1) return false;					// 待判断树为空不为任何树子结构；待判断树不空但树遍历到的节点为空是不行的
		if (judge(pRoot1, pRoot2)) return true;				// 判断两者的对应的位置值是否相同，相同则认为是子结构
		if(HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2)) 	// 迭代下一个节点
			return true;
		else 
			return false;
    }
};