前端 leetcde 算法面试套路之二叉树
前端就该用 JS 写算法 -- 树 -- 简单的那 30%
这里优先选择了 LeetCode 热题 HOT 100 中的树题,毕竟刷题的边际收益就是冲击需要算法的面试,所以 Hot 优先级更高。
二叉树的遍历
递归遍历
递归的时候前中后序都能直接处理完了
递归是前中后序遍历最简单也是最容易出理解的方法,不懂的画个图就好了
迭代遍历 -- 双色标记法
使用颜色标记节点状态,新节点为白色,已经访问的节点为灰色 -- 可以用数字或者其他任意标签标示
如果遇到的节点是白色,则标记为灰色,然后将右节点,自身,左节点一次入栈 -- 中序遍历
如果遇到的节点是灰色的,则将节点输出
注意这里是用 stack 栈来存储的,所以是后进先出,所以如果是中序遍历,左 - 中 - 右 ,那么在插入栈的时候要反过来 右 - 中 - 左
按照那个男人的指示,正常我们就用递归做就好,就好像我们做非排序题排序的时候,sort 一下就好了,但是一旦面试官问到用另外的迭代方式的时候,我们再套个模板,会比记住多个迭代写法要简单,毕竟内存容量有限,而后续遍历的迭代写法确实挺坑的,能省一点内存就省一点吧
144. 二叉树的前序遍历
1.94 二叉树的中序遍历
145. 二叉树的后序遍历
参考视频:传送门
101. 对称二叉树
分析
对称二叉树,其实是要求是否镜像对齐,所以递归过程至少需要两个根节点,然后 dfs 主要就是判断是否是对称的两棵树
这里是自顶向下分配相互比较的子树节点 left 和 right,然后再自底向上的返回最终结果
在某一次 dfs 中,如果比较双方都是 null,那么证明比较双方是对称的;如果出现只有一方有值,或者双方有值但是值不一样的时候,返回 false;
每次递归都是左右外层构成比较,左右内层构成比较
时间复杂度: O(h), 其中 h 是树的高度
104. 二叉树的最大深度
使用树的三种搜索方式,层序,自顶向下的 dfs,自底向上的递归 dfs
层序遍历
无论是深度,层数等,直接用层序遍历找到最后一层的最后一个叶子节点即可
时间复杂度 O(N), 空间复杂度 O(K) -- K 是最大宽度
dfs -- 自顶向下
我们在计算层数的时候,可以考虑到,没遍历一层,就携带一个参数,这个参数是一个标记,比方这里就是深度 depth
这样当我们遍历到叶子节点的时候,都可以和最大值比对一下,然后结束这一条路线
时间复杂度 O(N), 空间复杂度 O(D) -- D 是深度
递归 -- 自低向上
既然有自顶向下,那么当然就有自低向上了;
就我浅薄的算法能力而已,自顶向下就是带参数的深度优先遍历 DFS, 而自低向上,是递归,需要 dfs 到了底部,然后归到根节点,所以这里用的是 recursion 作为方法名。
自顶向下是从根节点开始算一层深度,然后跑到叶子节点结束;自低向上反过来,跑到最底层,然后不断求叶子结点的最大深度,然加上自身返回到上层
时间复杂度 O(N), 空间复杂度 O(1)
226. 翻转二叉树
自底向上
因为要求的是反转二叉树,对于任意一颗子树,其实都是要做一样的操作,所以可以先递到叶子节点,然后开始进行翻转
自底向上将翻转好的子树传递到上层的节点,直到最后的根节点,得到了两课翻转好的树,然后交换一下一下位置就好了
时间复杂度 O(N)
评论