lol门户网站源码,黄山风景区,清镇网站建设推广,深圳公司黄页企业名录文章目录 写在前面Tag题目来源题目解读解题思路方法一#xff1a;递归方法二#xff1a;迭代 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 专栏内容以分析题目为主#xff0c;并附带一些对于本题… 文章目录 写在前面Tag题目来源题目解读解题思路方法一递归方法二迭代 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【递归】【迭代】【二叉树】 题目来源
100. 相同的树 题目解读
判断两棵二叉树是否相同相同不仅要在结构上相同还要在对应节点值上相同。 解题思路
有两种解决思路一是递归而是迭代。
在真正理解的递归的含义之后会发现不论是从代码量还是思考量递归算法都更胜一筹。而迭代虽易于理解但是代码量较大。
方法一递归
思路
我们从根节点开始判断两棵二叉树是否相同可以发现如果根节点的值相同并且结构相同左右子树都有那么只需要判断两棵树的左右子树是否相同即可。
标准的大问题转化成了子问题都是判断两棵树是否相同只是范围缩小了。于是可是使用递归来解题。
递归出口是什么
递归出口换言之就是可以直接进行判断的情况包括
节点都为空此时可以直接返回 true一个节点为空另一个不为空返回 false节点值不相等返回 false。
大问题与子问题的如何链接
本题是判断二叉树是否相同如果对应的子二叉树不同则 “大” 二叉树也不同。
算法
我们从根节点开始递归递归函数为
递归出口见上述对递归出口的描述递归比较左子树和右子树“大问题” 的比较结果即为小问题的比较结果。
/*** 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 isSameTree(TreeNode* p, TreeNode* q) {if(p nullptr q nullptr){return true;}else if(p nullptr || q nullptr){return false;}else if(p-val ! q-val){return false;}else{return isSameTree(p-left, q-left) isSameTree(p-right, q-right);}}
};复杂度分析
时间复杂度 O ( m i n ( m , n ) ) O(min(m, n)) O(min(m,n)) m m m 和 n n n 分别为两个二叉树的节点数。
空间复杂度 O ( m i n ( m , n ) ) O(min(m, n)) O(min(m,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 isSameTree(TreeNode* p, TreeNode* q) {if(p nullptr q nullptr){return true;}else if(p nullptr || q nullptr){return false;}queueTreeNode* q1, q2;q1.push(p);q2.push(q);while(!q1.empty() !q2.empty()){TreeNode* now1 q1.front();q1.pop();TreeNode* now2 q2.front();q2.pop();// 两个节点值不同if(now1-val ! now2-val){return false;}auto left1 now1-left, right1 now1-right, left2 now2-left, right2 now2-right;// 左/右子树一个为空另一个不为空if((left1 nullptr) ^ (left2 nullptr)){return false;} if((right1 nullptr) ^ (right2 nullptr)){return false;}// 更新队列if(left1) q1.push(left1);if(right1) q1.push(right1);if(left2) q2.push(left2);if(right2) q2.push(right2);}return q1.empty() q2.empty();}
};复杂度分析
时间复杂度 O ( m i n ( m , n ) ) O(min(m, n)) O(min(m,n)) m m m 和 n n n 分别为两个二叉树的节点数。
空间复杂度 O ( m i n ( m , n ) ) O(min(m, n)) O(min(m,n))。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
