题解 | #树的子结构#

//这道题的思路，看到判断B是不是A的子结构，其实就是在比较B与A的某个子树是否一致。因此在局部上，这基本是个比较两棵二叉树是否相等的问题。用solve函数正常的递归解决就行。唯一需要注意的是可以允许A戛然而止，比如A后面还有更多的孙子节点，但只要到目前为止都与B相同就行了。因此需要在solve函数中处理B==nullptr的情况。
//而在宏观上，我们需要把A的子树一个个抓出来与B做比较。找到A的所有子树其实就是遍历A树的所有节点，因此在宏观上还要再写一个前序遍历来调用solve函数。
//完。
class Solution {
public:
	//可以将这个问题转化为求两棵树是否长得一样的问题。
	bool solve(TreeNode* A,TreeNode* B)
	{
		bool current=false;
		//因为毕竟求的是子树，是可以允许A有后续节点，B没有后续节点的情况的。
		if (B==nullptr) 
		{
			return true;
		}
		else if(A==nullptr && B!=nullptr)
		{
			//这种情况不被允许。
			return false;
		}
		else 
		{//A!=nullptr && B!=nullptr
			if (A->val==B->val) {
				current=true;//在都不为空的情况下，值相等便为要求。
			}else {
				current=false;
			}
		}
		//递归
		return current && solve(A->left, B->left) && solve(A->right, B->right);
	}

	bool FrontOrder(TreeNode* pRoot1, TreeNode* pRoot2)
	{
		if(pRoot1==nullptr)
			return false;
		if (solve(pRoot1,pRoot2)) 
		{//如果在当前节点出发能得到匹配的子树，就到此为止。
			return true;
		}
		//否则要继续遍历A树。看看A树上有没有与B树相同的子树。
		bool left=FrontOrder(pRoot1->left, pRoot2);
		if(left)return true;
		bool right=FrontOrder(pRoot1->right, pRoot2);
		return right;
	}

    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
		if (pRoot1==nullptr|| pRoot2==nullptr) {
			return false;
		}
		return FrontOrder(pRoot1, pRoot2);
    }
};