讲道理的豹子说这不是bug

分类

/ 注册

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

刷题题解（c++）

96篇文章 900人学习

算法知识总结

3篇文章 859人学习

全部文章（共100篇）

题解 | #二叉树的镜像# 来自专栏

方法：递归二叉树的镜像就是将二叉树的每个结点都交换它的左右子结点。1、交换根结点的左右子结点；2、进入左子树和右子树不断地向下交换根结点的左右子结点。时间复杂度：o(n)空间复杂度：o(n)，递归栈的深度。 class Solution { public: TreeNode* Mirro...

2023-07-18

1 177

题解 | #合并二叉树# 来自专栏

方法：递归将问题分解为，合并当前结点和合并当前结点的两个二叉树两个部分。可以运用递归进行合并。时间复杂度：o(min(n,m))，m和n分别为两棵树的节点树，当一个树访问完时，自然就连接上另一个树的节点，故只访问了小树的节点数。空间复杂度：o(min(n,m))，递归栈深度也同时间，只访问了小树的节...

2023-07-18

1 358

题解 | #对称的二叉树# 来自专栏

方法一：递归一个对称的二叉树，两个不同方向的前序遍历一定是相同的。通过递归进行两个方向的遍历，终止条件为：当两个节点只有一个为空，或者两个节点的值不相同，则二叉树不对称。时间复杂度：o(n)空间复杂度：o(n)。递归栈的深度 class Solution { public: bool i...

2023-07-18

1 326

题解 | #二叉树中和为某一值的路径(一)# 来自专栏

方法：递归既然是检查从根到叶子有没有一条等于目标值的路径，那肯定需要从根节点遍历到叶子，我们可以在根节点每次往下一层的时候，将sum减去节点值，最后检查是否完整等于0. 而遍历的方法我们可以选取二叉树常用的递归前序遍历，因为每次进入一个子节点，更新sum值以后，相当于对子树查找有没有等于新目标值的路...

2023-07-09

1 349

题解 | #二叉树的最大深度# 来自专栏

方法：递归二叉树从根节点每次往下一层深度就会加1。因此二叉树的深度就等于根节点这个1层加上左子树和右子树深度的最大值：max_depth = max(left_depth, right_depth) + 1，因此可以用递归分解为子问题。时间复杂度：o(n)空间复杂度：o(n) class Solut...

2023-07-08

1 302

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

方法一：递归二叉树的后序遍历顺序：左节点->右节点->根节点。先依次进入左右子树进行递归，再保留根节点的值。时间复杂度：o(n)。需要遍历二叉树的所有节点，需要o(n)。空间复杂度：o(n)。需要开辟空间保存中序遍历的节点值。 class Solution { public: v...

2023-07-08

1 368

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

方法一：递归二叉树的中序遍历顺序：左节点->根节点->右节点。先递归遍历左子树，再保存根节点的值，再递归遍历右子树。时间复杂度：o(n)。需要遍历二叉树的所有节点，需要o(n)。空间复杂度：o(n)。需要开辟空间保存中序遍历的节点值。 class Solution { public:...

2023-07-08

1 375

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

方法一：递归二叉树的前序遍历顺序：根节点->左节点->右节点。先保存根节点的值，依次进入左右子树进行递归。时间复杂度：o(n)。需要遍历二叉树的所有节点，需要o(n)。空间复杂度：o(n)。需要开辟空间保存前序遍历的节点值。 class Solution { public: ...

2023-07-08

1 375

题解 | #比较版本号# 来自专栏

方法：双指针使用两个指针分别指向两个数组的头元素，分别得到两个点号之间的数字，通过比较两个数字的大小即可得到两个版本号的大小。时间复杂度：o(n)空间复杂度：o(1) class Solution { public: int compare(string version1, string...

2023-07-08

2 359

题解 | #数组中的逆序对# 来自专栏

方法：归并排序题目中要求得出一个数组的所有逆序对（前面的数大于后面的数组成一个逆序对），归并排序将数组向下拆分至单个元素的数组，然后向上递归，不断地合并两个数组，直到将整个数组完成排序。如果是两个有序的数组，我们就可以很容易得到该元素逆序对的数目，而不用一个个进行遍历比较。时间复杂度：o(nlogn...

2023-07-08

1 304