💓 博客主页：倔强的石头的CSDN主页 

             📝Gitee主页：倔强的石头的gitee主页

   ⏩ 文章专栏：《数据结构与算法 经典例题》C语言

                                  期待您的关注

目录

一、问题描述

二、解题思路

三、C语言实现代码 

---

 

一、问题描述

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

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

 

原题出自

100. 相同的树 - 力扣（LeetCode）

 

 

二、解题思路

解题思路:
通过递归调用，对两棵树的每一个节点进行判断

 

• 首先，如果两棵树的根结点都为NULL，说明这两棵树是相同的，都是空树，返回true
• 如果一棵树根结点为空，另一棵树根结点不为空，说明两棵树结构是不同的
• 如果上述条件没有执行，再来判断节点的值:但这里要注意，判断两棵树节点的值相同返回true不可行，因为即使根结点值相同，还需要对子树继续进行判断；所以这里改成判断两棵根结点的值不相同就返回false
• 如果上述条件都没有执行，说明根结点既不为空，结构和值也相同，对子树继续判断——分别将两棵树的左右指针指向的节点作为参数进行递归调用，如果两个函数都返回true，则返回true（如果两棵树相同，函数会一直调用，直到左右指针都指向NULL，会逐步返回true回归；否则任何一步出现false，都会往回逐步返回false）

 

 

三、C语言实现代码 

struct TreeNode {int val;struct TreeNode* left;struct TreeNode* right;};
typedef struct TreeNode TNode;
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{if (p == NULL && q == NULL)//是否都为空return true;if (p == NULL || q == NULL)//判断当前节点的结构是否相同return false;if (p->val != q->val)//判断当前节点的值是否相同return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);}