文和906

分类

未归档(4) 项目笔记(5) 题解(103)

/ 注册

全部文章（共113篇）

题解 | #二叉搜索树的后序遍历序列#

刚看到题目尝试使用迭代的方法来找规律逐个元素判断，写到后面发现情况太过复杂，还是递归来的方便。总体思路是后序遍历的搜索树，其最后一个结点为头结点，而前面的数列则可根据该头结点分为连续的两部分，一部分笔比该结点大，一部分比该结点小。这样就得到了基本的拆分思路，每次都找到数列最后一个数，然后找到数列...

C++ 二叉搜索树递归

2021-10-09

0 364

题解 | #从上往下打印二叉树#

二叉树的层序遍历，较为基础。首先用一个二维数组将不同层的结点分开保存，然后将该二维数组的数依次输入到结果数组中即可。遍历过程中使用一个level变量来传递层数信息。 /* struct TreeNode { int val; struct TreeNode *left; struct Tree...

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

2021-10-08

0 410

题解 | #二叉树的镜像#

开始看到题目中说有原地算法，想挑战一下的，但是想了一会没什么思路，还是用常规的遍历解法来做了。逻辑十分简单，遍历头结点，交换左右子树，再依次遍历左右子树，直到遍历所有结点。使用递归进行遍历，时间复杂度为O(n)，同时需要维护一个递归栈，空间复杂度为O(n),满足题目要求。 /** * stru...

C++ 二叉树

2021-10-08

0 398

题解 | #树的子结构#

这题的基本思路很简单，难在对于情况的判断。上来看题首先确定题目中要遍历二叉树，并且还需要一个方法来判断是否有相同的结构。注意，这里判断的逻辑与判断两树是否相同基本类似。处理起来就是通过遍历原始树的结点，对每一个结点都调用判断结构的方法，若找到一个结点返回true，则直接返回true。这里说一下判断两...

C++ 二叉树分治链表

2021-10-08

0 378

题解 | #重建二叉树#

看题目首先确定采用分治的思想，通过题目给出的先序遍历与中序遍历确定头结点，然后通过该头结点得到两个子树的先序遍历与中序遍历，重复该过程，最后就可以得到完整的树。具体实现中采用递归的方法，递归的最大栈深度为n，在递归中有一步需要循环来查找头节点，平均时间复杂度为O(logn)，故该方法时间复杂度为O...

C++ 动态规划链表二叉树

2021-10-08

0 376

题解 | #二叉搜索树的第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 378

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

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

C++ 链表

2021-09-30

0 446

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

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

C++ 链表

2021-09-30

0 430