Leetcode 刷题记录 | fufu酱のNoteBook

type

status

slug

summary

树

刷题路径

前言

本章目标：

理解和区分树的遍历方法

能够运用递归方法解决树的前序遍历、中序遍历和后序遍历问题

能用运用迭代方法解决树的前序遍历、中序遍历和后序遍历问题

能用运用广度优先搜索解决树的层序遍历问题

树的遍历

pre_order首先访问根节点，然后遍历左子树，最后遍历右子树

in_order首先遍历左子树，然后访问根节点，最后遍历右子树

post_order首先遍历左子树，然后遍历右子树，最后访问根节点

😋

称为前中后的原因是因为根节点的遍历顺序是前中后

二叉树的层序遍历

运用递归解决树的问题

通常我们可以采用“自顶向下”或者是“自底向上”的方法来解决树的递归问题

自顶向下的解决方式(top-down)

“自顶向下” 意味着在每个递归层级，我们将首先访问节点来计算一些值，并在递归调用函数时将这些值传递到子节点。所以 “自顶向下” 的解决方案可以被认为是一种前序遍历。
我们知道根节点的深度是1。对于每个节点，如果我们知道某节点的深度，那我们将知道它子节点的深度。因此，在调用递归函数的时候，将节点的深度传递为一个参数，那么所有的节点都知道它们自身的深度。而对于叶节点，我们可以通过更新深度从而获取最终答案。

自底向上的解决方法

“自底向上” 是另一种递归方法。在每个递归层次上，我们首先对所有子节点递归地调用函数，然后根据返回值和根节点本身的值得到答案。这个过程可以看作是后序遍历的一种。

莫里斯算法解决树的问题

有一种巧妙的方法可以在线性时间内，只占用常数空间来实现前序遍历。这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出，因此被称为 Morris 遍历。

Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其前序遍历规则总结如下：

新建临时节点，令该节点为 root；

如果当前节点的左子节点为空，将当前节点加入答案，并遍历当前节点的右子节点；

如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点：

如果前驱节点的右子节点为空，将前驱节点的右子节点设置为当前节点。然后将当前节点加入答案，并将前驱节点的右子节点更新为当前节点。当前节点更新为当前节点的左子节点。

如果前驱节点的右子节点为当前节点，将它的右子节点重新设为空。当前节点更新为当前节点的右子节点。

重复步骤 2 和步骤 3，直到遍历结束。

这样我们利用 Morris 遍历的方法，前序遍历该二叉树，即可实现线性时间与常数空间的遍历。

作者：力扣官方题解链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/461821/er-cha-shu-de-qian-xu-bian-li-by-leetcode-solution/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

144. 二叉树的前序遍历

94. 二叉树的中序遍历

145. 二叉树的后序遍历

102. 二叉树的层序遍历

这个题目属于模版题，还是有点挑战的。有一些需要注意的细节点：

判断节点的时候一定需要采用`≠NULL`，而不是直接！root这样是过不去测试点的

注意复习多重指针的运用，还有malloc的用法，这道题目还是比较tricky的

还需要注意的就是层次排序是和队列挂钩的，判断弹出的条件

104. 二叉树的最大深度

很简单的题目，注意判断条件，以及返回的数+1就可以

101. 对称二叉树

注意这道题目递归的思路，首先判断初始条件，如果这个根是NULL，那么直接返回true

然后新生成一个辅助函数进行判断，判断true还是flase，如果只要出现了一个false那么整个式子就是false的

112. 路径总和

想法是直接找到树的叶子，如果最后一个叶节点的值等于ragetsum的值，那么就返回true，否则就返回false,但是这种做法会出现到题目中的一个坑点，如果root本身就是空，然后直接判断是不是等于0，就会导致判断是true导致结果错误，因此我们可以一直判断到叶节点，然后进行进一步的判断，而判断叶节点的条件也还是非常容易的，同时检查他的左节点和右节点是不是等于NULL就可以判断出结果了

回溯

考虑直接正向相加的模式

1. 两数之和

暴力求解

思路很容易想到，但是算法的时间复杂度比较高

哈希表

算出当前数字和目标数字的差

检查哈希表中是否存在该差，如果存在就返回，如果不存在，就把数字的值和index索引存入该哈希表中

当前的数字作为key，角标作为value存入哈希表中

106. 从中序与后序遍历序列构造二叉树

后序数组为0，代表空节点

后序数组的最后一个节点就是所构建的二叉树的根节点的值

根据根节点的值找到它在中序数组中的索引值的大小

对中序数组，后序数组进行分割，然后在这个的基础上进行递归

递归（左子树，右子树）

105. 从前序与中序遍历序列构造二叉树

116. 填充每一个节点的下一个右侧指针(完美二叉树）

117. 填充每一个节点的下一个右侧指针(完美二叉树）

在完成这道题目的时候，我们需要思考题目中的要求是让我们把一层中所有的节点连接起来，那么我们可以站在什么角度去思考这个问题才最简单呢？假如我们需要在第三层进行连接节点，那么我们直接在第三层进行处理，找寻下一层节点将会是一个巨大的困难，因此我们可以站在这一层的上面一层的视角来思考这个问题，就可以发现我们可以采用队列+链表的角度去思考这个问题，然后就可以很轻松的来解决这个问题了。注意终止条件，以及队列的出入。

236. 二叉树的最近公共祖先

递归的做法思路十分简洁直接进行判断，将问题拆分为左子树和右子树的问题，如果找不到直接return NULL就行，如果两边都是NULL，那么就是交界之处。

297. 二叉树的序列化与反序列化

首先学习了字符串的知识点：

strcat(ans,str) 将str剪切到ans函数的后方
sprintf(string,”%s%d”,ans,data) 强制类型转换
strcpy，strcmp 等一系列字符串常用函数
字符串函数 atoi 把字符串转换为整型数

malloc 和 calloc 还有 realloc 函数的区别：

在内存的动态存储区中分配一块长度为size字节的连续区域，参数size为需要内存空间的长度，返回该区域的首地址
与malloc相似,参数sizeOfElement为申请地址的单位元素长度,numElements为元素个数，即在内存中申请numElements*sizeOfElement字节大小的连续地址空间.
给一个已经分配了地址的指针重新分配空间,参数ptr为原有的空间地址,newsize是重新申请的地址长度.
主要区别：

函数malloc不能初始化所分配的内存空间差，但是calloc会将分配的内存空间的每一位保证初始化为0
realloc可以对给定的指针所指的内存空间进行放大或者缩小

首先还是dfs先序遍历进行编码，把树中的节点写入到字符串中，然后进行递归返回，下面再重新建树的过程中，把节点的值传递给节点，遇到@进行返回NULL操作，本质还是递归，dfs直接递归，bfs使用队列进行操作。

95.不同的二叉搜索树

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

动态规划 dp

7.爬楼梯

暴力递归（时间复杂度过高）

动态规划，使用数组进行储存，空间复杂度和时间复杂度都是O(n)

采用数学公式进行推导：

1137. 第N个斐波拉契

118&119 杨辉三角

本质上是一样的东西

23. 合并K个升序链表

这个是暴力算法，能跑就是胜利，关键是直接调用c语言库里面的stdio.h库的qsort

上面的算式是按照升序模式进行排列，如果是调换位置，那么就是降序排列

接下来输入 qsort(nums, length, sizeof(int), cmp 就可以实现排列了。

回溯类题目的套路

使用数组path记录路径上的数字

集合s记录剩余未选的数字

只要是分叉大于2的树，节点的个数一定是小于n!

或者使用哈希表，如果该节点不在路径中就可以选择，然后再恢复现场

第一种做法类似于这样

首先还是经典的dfs，然后如果达到临界条件的情况下，就使用swap函数然后进行调换

还有一种是直接使用哈希表的做法，创建一个路径，如果访问了就跳过，如果没有访问那就继续