二叉树OJ题:LeetCode--100.相同的树

简介: 二叉树OJ题:LeetCode--100.相同的树

1.题目介绍

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

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

2.实例演示

简单的来说就是来判断两棵二叉树的对应结点是否完全相同。

3.解题思路

判断两棵二叉树是否相等最先想到的方法就是遍历,使用结点依次比较,那么二叉树的遍历方法有许多:

1. 前序遍历:根节点、左子树、右子树

2. 中序遍历:左子树、根节点、右子树

3. 后序遍历:左子树、右子树、根节点

4. 层序遍历:一层一层遍历二叉树

以上内容可以参考:https://blog.csdn.net/Yikefore/article/details/130859450?spm=1001.2014.3001.5501

那么该选用哪种遍历二叉树的方法呢? 前序遍历是比较合适的,因为前序遍历首先访问的就是根节点,如果两棵树的根节点都不相等那么就没有必要再继续往下面进行比较了,那么关于这道题最终还是要归为这棵树的子问题,也就是它的左右子树,所以使用递归实现。

在做题时要注意几个问题:

1. 结束标志--两棵树为空树、结点不相等

2. 若两棵树都为空,需要返回true,两棵树都为空满足相同的结点

3. 有一棵树为空,另一棵树不为空,就需要结束

代码实现:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
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);
}

代码解读:

首先我们对两棵树进行检查,判断两棵树是否都为空树,如果两棵树都为空树,即两棵树相等,即可返回true,如果两棵树都不为空,进行下一步的判断其中只有一棵树为空,若其中只有一颗树为空,那么表示两棵树不相等,即可返回false,若两棵树都不为空,即可判断它们的结点是否相等,若不相等,直接返回false,若相等,则直接递归判断它们的左右子树,又重新转化为了子问题,直到将两颗树全部遍历完毕。

递归展开图:

朋友们、伙计们,美好的时光总是短暂的,我们本期的的分享就到此结束,最后看完别忘了留下你们弥足珍贵的三连喔,感谢大家的支持!  

目录
相关文章
|
2月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
26 2
|
2月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
20 2
|
2月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
21 0
|
2月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
15 0
|
2月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
23 0
|
2月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
22 0
|
2月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
19 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
63 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
125 2