前往小程序,Get更优阅读体验!
立即前往
发布
社区首页 >专栏 >【数据结构与算法 经典例题】判断两棵二叉树是否相同

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

作者头像
用户11396077
发布2024-12-06 19:23:30
发布2024-12-06 19:23:30
1070
举报
文章被收录于专栏:C/C++指南

一、问题描述

给你两棵二叉树的根节点 pq ,编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 原题出自 100. 相同的树 - 力扣(LeetCode)

ee7834d0cd9c4f289b089bb3bf0aa72e.jpeg
ee7834d0cd9c4f289b089bb3bf0aa72e.jpeg

二、解题思路

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

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

三、C语言实现代码

代码语言:javascript
复制
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);

}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-07-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、问题描述
  • 二、解题思路
  • 三、C语言实现代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档