文和906

题解

未归档(4) 项目笔记(5)

/ 注册

全部文章 / 题解（共103篇）

题解 | #二叉搜索树的第k个结点#

由于是二叉搜索树，所以一个结点左边的数都比该结点小，右边的数都比该结点大。所以可以通过递归，按照中序遍历的顺序，先找到最左边的结点，该结点即为最小结点。然后开始计数，遍历到的第k个结点即为第k小结点。这样做仅递归遍历了一次链表，大部分情况是不用遍历整个链表的，所以时间复杂度小于等于O(n)。递归...

C++ 二叉搜索树链表

2021-09-30

0 409

题解 | #按之字形顺序打印二叉树#

基础层序遍历题。在最基本的层序遍历之上增加了隔层逆序的条件。解题思路是先层序遍历链表，在得到层序遍历好的结果数组后，遍历该数组，遇到偶数层就逆序。循环最多为一重，时间复杂度为O(n)。递归层序遍历链表时栈深度为n，空间复杂度为O(n)。符合题目要求。 /* struct TreeNode { ...

C++ 二叉树广度优先搜索

2021-09-30

0 426

题解 | #二叉树的深度#

递归深度优先遍历计算树深度。 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {...

C++ 递归二叉树深度优先搜索

2021-09-30

0 379

题解 | #删除链表中重复的结点#

基本思想是遍历链表，当下一个结点的值与本结点相同时，继续查看下一个结点，直到找到一个结点与本结点的值不同，将上一结点的next域指向不同的结点，从而完成将重复结点从链表中去除的需求。需要注意的是，当列表头结点重复时需要特殊处理。一半的代码都是头结点的特殊处理，有能力的朋友可以尝试优化代码结构。 /...

C++ 链表

2021-09-30

0 447

题解 | #复杂链表的复制#

在不限制时间复杂度的情况下，这题难度并不高。首先遍历一次链表来深拷贝出一个新链表，这次深拷贝不考虑random的值，仅将链表的label和next深拷贝出来。这样就得到了链表的基本骨架。再用一个二重循环遍历链表，每次处理一个结点，通过一个循环来从骨架链表中找到一个label域和原链表中ramdom...

C++ 链表

2021-09-30

0 430

题解 | #链表中倒数最后k个结点#

先遍历得出链表长度len，然后将链表头指针后移n-k个结点即可。时间复杂度为O(n)，空间复杂度为O(1)。 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), nex...

C++ 链表

2021-09-30

0 386

题解 | #两个链表的第一个公共结点#

从题目中可以看到，公共结点都是插入在不同结点之后的。所以先遍历两个链表得到链表长度，将长链表的后指针后移，直至两链表长度相等，然后比较两链表头指针，相等则返回，不等则同时后移一位,最终可得结果。这样做最多只有一重循环，时间复杂度为O(n)。只使用了两个临时变量保存用于遍历的指针，两个临时变量用于...

C++ 链表

2021-09-30

0 378

题解 | #合并两个排序的链表#

链表的归并排序。对第一个结点需要特殊处理。每次比较链表两个指针的值，将值小的放入结果链表，并将其指针后移。这样做是直接照搬数组的归并排序。 /* struct ListNode { int val; struct ListNode *next; ListNode(int x)...

C++ 链表归并排序

2021-09-29

0 450

题解 | #从尾到头打印链表#

递归遍历链表，倒序输出。 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) {...

C++ 链表栈

2021-09-29

0 324

题解 | #链表中环的入口结点#

比较固定的解法。先判定给定链表是否有环，若有则进而找环入口。使用快慢指针来判断链表是否有环。两指针都从头结点开始，快指针一次走两步，慢指针一次走一步，若两指针相遇，则有环，若其中一个指针为null，则无环。当链表中有环时，将两指针的其中一个指向头结点，另一指针继续指向相遇结点，然后两指针每次走一步，...

C++ 链表

2021-09-29

2 455