首页 > 代码库 > 020给定两个二叉树T1,T2判断T1是否是T2的子树(keep it up)

020给定两个二叉树T1,T2判断T1是否是T2的子树(keep it up)

给定两个二叉树T1,T2判断T1是否是T2的子树
首先在T2中查找T1的根节点,如果找不到,
则T1不是T2的子树,如果能找到,我们可以
遍历T1,检查T1的每个结点是否对应的存在T2

中。

代码:

struct TreeNode
{
	int data;
	TreeNode* leftChild;
	TreeNode* rightChild;
};

bool isExited(const TreeNode* vRoot1, const TreeNode *vRoot2, TreeNode* vRes)
{
	if (vRoot1 == NULL) return false;

	if (vRoot2 == vRoot1) 
	{
		vRes = vRoot1;
		return true;
	}

	bool Flag = false;
	Flag = isExited(vRoot1, vRoot2->leftChild, vRes);
	if (!Flag)
	{
		Flag = isExited(vRoot1, vRoot2->rightChild, vRes);
	}
	return Flag;
}

bool isSame(const TreeNode* vRoot1, const TreeNode *vRoot2)
{
	if (vRoot1 == NULL && vRoot2 == NULL) return true;
	if (vRoot1 != vRoot2) return false;
	bool Flag = isSame(vRoot1->leftChild, vRoot2->leftChild);
	if (!Flag) return false;
	Flag = isSame(vRoot1->rightChild, vRoot2->rightChild);
	return Flag;
}

bool isSubTree(const TreeNode* vRoot1, const TreeNode *vRoot2)
{
	TreeNode* Temp = NULL; //保存在T2中的位置
	if (!isExited(vRoot1, vRoot2, Temp)) return false;
	return isSame(vRoot1, Temp);
}


020给定两个二叉树T1,T2判断T1是否是T2的子树(keep it up)