讲道理的豹子说这不是bug

分类

/ 注册

TA的专栏 99篇文章 6人订阅

刷题题解（c++）

96篇文章 900人学习

算法知识总结

3篇文章 859人学习

全部文章（共100篇）

题解 | #输出二叉树的右视图# 来自专栏

方法：递归、BFS（层序遍历）二叉树的右视图就是二叉树每一层的最右结点。具体方法：1、利用递归使用前序和中序遍历重建二叉树；2、对重建后的二叉树进行层序遍历，将每一层的最后一个元素存入数组中，层序遍历完成后就得到二叉树的右视图时间复杂度：o(n)空间复杂度：o(n) class Solution {...

2023-07-23

1 306

题解 | #重建二叉树# 来自专栏

方法：递归对于二叉树的前序遍历，我们知道序列的第一个元素必定是根节点的值，因为序列没有重复的元素，因此中序遍历中可以找到相同的这个元素，而我们又知道中序遍历中根节点将二叉树分成了左右子树两个部分。具体做法：step 1：先根据前序遍历第一个点建立根节点。step 2：然后遍历中序遍历找到根节点在数组...

2023-07-22

1 315

题解 | #在二叉树中找到两个节点的最近公共祖先# 来自专栏

方法一：DFS、路径比较1、利用深度优先搜索分别获取两个结点在二叉树中的路径；2、比较两个路径，得到最后相同的的结点即为两个结点的最近公共祖先。时间复杂度：o(n)。最坏情况需要遍历二叉树所有节点空间复杂度：o(n)。 class Solution { public: bool flag...

2023-07-22

1 318

题解 | #判断是不是完全二叉树# 来自专栏

方法：BFS，辅助队列本质是广度优先搜索，利用辅助队列进行层序遍历。如果一个二叉树是完全二叉树，那么层序遍历时，第一个空结点也是它的最后一个空结点；否则就不是完全二叉树。时间复杂度：o(n)。最坏情况需要遍历二叉树的所有结点。空间复杂度：o(n)。需要辅助队列进行二叉树的层序遍历 class Sol...

2023-07-22

2 310

题解 | #判断是不是二叉搜索树# 来自专栏

方法一：递归二叉搜索树的中序遍历一定是升序数组，所以可以利用递归遍历二叉树，如果前一个结点一定小于当前的结点，则可以判断二叉树为二叉搜索树；否则判断为非二叉搜索树。时间复杂度：o(n)。空间复杂度：o(n)。 class Solution { public: //初始化前结点值为最小值 ...

2023-07-22

1 417

题解 | #二叉搜索树与双向链表# 来自专栏

方法：递归（中序遍历）对于二叉搜索树，中序遍历从小到大排序。通过递归实现二叉搜索树的中序遍历，并且改变结点的指针即可得到双向链表。时间复杂度：o(n)空间复杂度：o(n) class Solution { public: TreeNode* head = nullptr; Tre...

2023-07-20

1 325

题解 | #按之字形顺序打印二叉树# 来自专栏

方法：辅助队列本质依然是广度优先搜索（BFS），与层序遍历本质相同，只是在偶数层时需要进行翻转。时间复杂度：o(n)空间复杂度：o(n) class Solution { public: vector<vector<int> > Print(TreeNode* p...

2023-07-20

1 324

题解 | #求二叉树的层序遍历# 来自专栏

方法：辅助队列层序遍历本质就是广度优先搜索（BFS），通过构建辅助队列可以很好的得到二叉树的层序遍历。时间复杂度：o(n)空间复杂度：o(n) class Solution { public: vector<vector<int> > levelOrder(Tre...

2023-07-20

1 336

题解 | #二叉搜索树的最近公共祖先# 来自专栏

方法一：搜索路径比较得到两个目标值在二叉搜索数的路径，对两个路径进行比较，最后一个相同的结点就是最近的公共祖先时间复杂度：o(n)空间复杂度：o(n)。需要辅助队列存储路径 class Solution { public: //获取从根节点到目标值的路径 queue<Tre...

2023-07-19

1 336

题解 | #判断是不是平衡二叉树# 来自专栏

方法：递归（自顶向下）经过每个结点都得到它的左子树和右子树的最大深度，判断每个结点的左右子树深度差是否大于1。深度差不大于1则继续递归。时间复杂度：o(n2)。第一个递归遍历二叉树所有节点，第二个递归查找深度最坏情况下（二叉树退化为链表）需要遍历二叉树所有节点。空间复杂度：o(n) class So...

2023-07-19

1 317