网站圣诞问候特效网站快速查找

当前位置： 首页 > news >正文

网站圣诞问候特效,网站快速查找,店铺怎么做推广和宣传,山东省住房和城乡建设厅政务服务从LeetCode 100和101看二叉树的比较与对称性判断 今天要讲的是leetcode100.相同的树#xff0c;并且本文章还会讲到延伸题型leetcode101.对称二叉树。本文章编写用的是C语言#xff0c;大家主要是学习思路#xff0c;学习过后可以自己点击链接测试#xff0c;并且做一些对…从LeetCode 100和101看二叉树的比较与对称性判断 今天要讲的是leetcode100.相同的树并且本文章还会讲到延伸题型leetcode101.对称二叉树。本文章编写用的是C语言大家主要是学习思路学习过后可以自己点击链接测试并且做一些对应的生题现在就让我们开始吧 一、题目简介 LeetCode 100相同的树 给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。 示例 1 输入p [1,2,3], q [1,2,3] 输出true示例 2 输入p [1,2], q [1,null,2] 输出false示例 3 输入p [1,2,1], q [1,1,2] 输出false提示 两棵树上的节点数目都在范围 [0, 100] 内-104 Node.val 104 LeetCode 101:   对称二叉树 给你一个二叉树的根节点 root  检查它是否轴对称。 示例 1 输入root [1,2,2,3,4,4,3] 输出true示例 2 输入root [1,2,2,null,3,null,3] 输出false提示 树中节点数目在范围 [1, 1000] 内-100 Node.val 100 进阶你可以运用递归和迭代两种方法解决这个问题吗 二、思路详解 题目一LeetCode 100相同的树

1. 问题分析 这道题里有一个小坑如果我们单纯只通过遍历来比对是否相等的话是无法保证二叉树的结构相同的仅仅只能保证该颗二叉树所包含的节点数值是一致的但是我们将一颗树分为多个部分来比对就会方便很多将两棵树对应的左子树与左子树比对右子树和右子树比对。
2. 解题思路 我们可以使用递归的方法来解决这个问题。递归的基本思路如下 如果两个节点都为空返回 true。 如果一个节点为空而另一个不为空返回 false。 如果两个节点的值不同返回 false。 递归地比较左子树和右子树。
   
3. C语言实现 #include stdbool.h// 定义二叉树节点结构 typedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode right; } TreeNode;// 递归函数比较两个节点 bool isSameTree(TreeNode p, TreeNode* q) {// 如果两个节点都为空返回trueif (p NULL q NULL) {return true;}// 如果一个为空另一个不为空返回falseif (p NULL || q NULL) {return false;}// 如果两个节点的值不同返回falseif (p-val ! q-val) {return false;}// 递归比较左子树和右子树return isSameTree(p-left, q-left) isSameTree(p-right, q-right); } 题目二LeetCode 101对称二叉树
4. 问题分析 这道题与上一道题LeetCode 100相同的树是很相似但有两个关键的不同点 参数不同这道题只传入一个根节点即只有一棵树。 判断条件不同这道题要求判断的是对称二叉树即镜像相同。具体来说左子树的左节点应该与右子树的右节点相同左子树的右节点应该与右子树的左节点相同。
   
5. 解题思路 为了解决上述两个不同点我们可以通过构造一个新的函数来实现将一棵树“一分为二”再对两侧的左右子树进行比较。递归的基本思路如下 递归终止条件 如果两个节点都为空返回 true表示这部分是镜像对称的。 如果一个节点为空而另一个不为空返回 false表示这部分不对称。 递归逻辑 如果两个节点的值相同继续递归比较左子树的左节点与右子树的右节点以及左子树的右节点与右子树的左节点。 如果两个节点的值不同直接返回 false。
   
6. C语言实现 #include stdbool.h// 定义二叉树节点结构 typedef struct TreeNode {int val; // 节点的值struct TreeNode *left; // 指向左子节点的指针struct TreeNode right; // 指向右子节点的指针 } TreeNode;// 辅助函数检查两个节点是否镜像对称 bool check(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 check(p-left, q-right) check(p-right, q-left);}// 如果两个节点的值不同直接返回falsereturn false; }// 主函数判断整棵树是否对称 bool isSymmetric(struct TreeNode* root) {// 从根节点开始调用辅助函数检查整棵树是否对称return check(root, root); } 4.迭代法拓展 为了判断一棵二叉树是否对称我们还可以使用层次遍历BFS。由于二叉树的结构特性我们无法直接通过自身的遍历来实现层次遍历因此需要借助一个辅助数据结构——队列。队列可以帮助我们逐层比较左右子树的节点确保对称性。 #include stdbool.h// 定义二叉树节点结构 typedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode right; } TreeNode;// 使用迭代方法层次遍历判断二叉树是否对称 bool isSymmetric(struct TreeNode root) {// 如果根节点为空直接返回 true空树是对称的if (root NULL) return true;// 使用数组模拟队列struct TreeNode* queue[1000];// head 和 tail 分别指向队列的头部和尾部int head 0, tail 0;// 将根节点的左右子树加入队列queue[tail] root-left;queue[tail] root-right;// 循环结束条件队列为空head tailwhile (head ! tail) {// 从队列中取出两个节点进行比较struct TreeNode* leftNode queue[head];struct TreeNode* rightNode queue[head];// 如果一个节点为空而另一个不为空说明不对称返回 falseif (leftNode NULL rightNode ! NULL) return false;if (leftNode ! NULL rightNode NULL) return false;// 如果两个节点都为空跳过本轮循环继续下一对节点的比较if (leftNode NULL rightNode NULL) continue;// 如果两个节点的值不相等说明不对称返回 falseif (leftNode-val ! rightNode-val) return false;// 将左节点的左子节点和右节点的右子节点加入队列queue[tail] leftNode-left;queue[tail] rightNode-right;// 将左节点的右子节点和右节点的左子节点加入队列queue[tail] leftNode-right;queue[tail] rightNode-left;}// 如果队列为空且没有发现不对称的情况返回 truereturn true; } 好啦今天的leetcode每日一题就到这里啦欢迎大家点赞收藏一起进步我们明天见