leetcode 100.相同的树-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 100.相同的树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

涉及到递归，最好多画图理解，希望对你们有帮助

100.相同的树

题目

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

题目链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

文字和画图分析

思考递归进行的条件和结束的条件是什么

列举递归可能会出现的情况

针对上面两个问题进行解答：

要想找两个树的结构相同有点麻烦，换个思路，我们找它们不同

所以我们需要先对比两者的根节点，再去对比左子树和右子树

[很明显，我们采取的是前序遍历整个节点]

在递归的时候，每一次根节点都发生变化，只要根节点对应的数值不同，就返回 false 结束递归 (其中一种结束条件)

根节点相同，我们无法判断是否两个树结构相同，只能继续递归（这是递归条件）

递归期间，我们还可能碰到以下情况：

如上图：我们遇到空树了

这里还需要分两种情况讨论：

如果两个树在这个节点都是空，则返回 true (这是其中一种结束条件)

[注意：我们是先对比根，再对比左子树，最后对比右子树，所以只有左子树和右子树都为 true 才是一样的树]

如果两个树只有一个为空，则返回 false (这是其中一种结束条件)

3. 判断的顺序问题

由于可能会遇到空树，先比较根的大小明显是不行的，所以应该把比较是否是空树的条件放前面文章来源地址https://www.toymoban.com/news/detail-753822.html

代码

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    if ((p == NULL && q != NULL) || (p != NULL && q == NULL))
	{
		return false;
	}
	if (p == NULL && q == NULL)
	{
		return true;
	}
	if (p->val != q->val)
	{
		return false;
	}
	return isSameTree(p->left, q->left)  && 
	isSameTree(p->right, q->right);
}

到了这里，关于leetcode 100.相同的树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！