做怎么网站推广,91成长人版抖音安装,政务网站建设存在的问题,深圳网站建设信科网络文章目录 写在前面Tag题目来源解题思路方法一#xff1a;递归方法二#xff1a;迭代 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 专栏内容以分析题目为主#xff0c;并附带一些对于本题涉及到的… 文章目录 写在前面Tag题目来源解题思路方法一递归方法二迭代 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【递归】【迭代】【二叉树】 题目来源
101. 对称二叉树 解题思路
如果一棵树的左子树与右子树镜像对称那么这两棵树是对称的。
因此问题转换为两棵树在什么情况下是互为镜像的找出使两棵树互为镜像的条件根据条件即可结局对称问题。
镜像条件如下
两棵树的两个根节点具有相同的值每棵树的右子树都要与另一棵树的左子树镜像对称。
同时满足以上两个条件即可判断出两棵树是对称的。
二叉树问题通常都有两种递归和迭代的解法。
方法一递归
递归出口是什么
递归出口即可以直接判断的情况包括
两个节点都为空时直接返回 true一个节点为空另一个不为空返回 false。
如何往下递
当前的两个节点表示的子树是否是对称的取决于当前两节点的值以及左右子树是否对称。
只有当前两节点的值相等并且左右子树对称这两个节点表示的子树才是对称的。
算法
实现一个判断两个节点 p 和 q 表示的子树是否是对称的函数 check
如果 p nullptr 并且 q nullptr直接返回 true如果 p ≠ nullptr 或者 q ≠ nullptr直接返回 false最后 p 和 q 表示的子树是否是对称与 p-val q-val check(p-left, q-right) check(p-right, q-left) 一致直接返回该表达式。
调用 check(root, root) 即得到最终答案。
复杂度分析
时间复杂度 O ( n ) O(n) O(n) n n n 为二叉树中节点的数量。
空间复杂度 O ( n ) O(n) O(n)。
方法二迭代
思路与算法
使用迭代解法需要用到队列。
首先我们引入一个队列初始化时我们把根节点入队两次。每次提取两个节点并比较它们的值队列中每两个连续的节点应该是相等的而且它们的子树互为镜像然后将两个节点的左右子节点按相反的顺序插入队列中。
当队列为空时或者我们检测到树不对称即从队列中取出两个不相等的连续节点时该算法结束。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool check(TreeNode* u, TreeNode *v) {queueTreeNode* q;q.push(u); q.push(v);while (!q.empty()) {u q.front(); q.pop();v q.front(); q.pop();if (!u !v)continue;if (!u || !v ||(u-val ! v-val))return false;q.push(u-left);q.push(v-right);q.push(u-right);q.push(v-left);}return true;}bool isSymmetric(TreeNode* root) {return check(root, root);}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) n n n 为二叉树中节点的数量。
空间复杂度 O ( n ) O(n) O(n)因为二叉树中的节点最多入队、出队一次因此渐进的时间复杂度为 O ( n ) O(n) O(n)。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
