Leetcode-树的子结构

11.树的子结构

题目内容:

Leetcode-树的子结构

代码及思路:

树的构建部分我还没整明白,后面弄清楚了再补上构建树的部分,先贴上功能函数的实现部分。

class solution
{
	public:
		//输入的是两棵二叉树,因为约定空树不是任意一个树的子结构
		bool HasSubtree(TreeNode* p1, TreeNode* p2)
		{
			//若任意一个树为空,输出都为false(此处p1位题目中的A,p2为题目中的B)
			bool res = false;
			if (p1 != nullptr&&p2 != nullptr)
			{
				//首先在A树中查找与B树根节点相同的节点位置,然后再遍历子树
				if (p1->val == p2->val)
					res = Doeshassubtree(p1, p2); //再遍历子树,若某个节点处不相同,则继续在左右子树中寻找
				if (!res)
					res = HasSubtree(p1->left, p2);
				if (!res)
					res = HasSubtree(p1->right, p2);
			}
			return res;
		}
		//
		bool Doeshassubtree(TreeNode* root1, TreeNode* root2)
		{
			if (root2 == nullptr)
				return true;
			if (root1 == nullptr)
				return false;
			if (root1->val != root2->val)
				return false;
			return Doeshassubtree(root1->left, root2->left) && Doeshassubtree(root1->right, root2->right);//分别依次比较左右子树
		}
};

 

上一篇:【Offer】[26] 【树的子结构】


下一篇:LeetCode 951. Flip Equivalent Binary Trees