【数据结构与算法】判断两棵二叉树是否相同

​

目录

一、问题描述

二、解题思路

三、C语言实现代码 

一、问题描述

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

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

二、解题思路

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

• 首先，如果两棵树的根结点都为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);

}

​