第四阶段算法学习总结
2020-09-14 本文已影响0人
huxq_coder
脑图：http://naotu.baidu.com/file/3bc98871b57aa37136f7db9c7c603376?token=7a4113ffec3d8fba
94.二叉树的中序遍历
左中右
- 递归
递归左节点
输出中节点的值
递归右节点 - 迭代
利用辅助栈保存节点
while 当前节点存在
入栈当前节点
移动到左节点
当前节点不存在，出栈栈顶元素，输出元素的值，移动到右节点
详细题解：https://www.jianshu.com/p/6d892b6aed0a
144.二叉树的前序遍历
中左右
- 递归
输出当前节点的值
递归左节点
递归右节点 - 迭代
入栈跟节点
while 当前节点是否为空
出栈栈顶元素，输出栈顶元素的值
入栈右节点
入栈左节点（栈：FILO，后入左，先出左）
详细题解：https://www.jianshu.com/p/6a1e41297599
590.N叉树的后序遍历
从左至右，从下往上
- 递归
是否有子节点
无，输出当前节点的值
有，遍历递归子节点 - 迭代
辅助栈，输出结果集为双端队列
入栈跟节点
while 当前节点不为空
弹出栈顶元素，双端队列头插该元素的值
遍历该元素的子节点，入栈
详细题解：https://www.jianshu.com/p/33e9bf5d4a85
589.N叉树的前序遍历
从上往下，从左向右
- 递归
入栈根节点
弹出栈顶节点，输出该节点的值
遍历递归该节点的子节点 - 迭代
入栈跟节点
while 当前节点是否为空
出栈栈顶节点，输出该节点的值
倒序遍历入栈子节点
详细题解：https://www.jianshu.com/p/2e8b5b9876bf
429.N叉树的层序遍历
从上往下
从左向右（作为集合输出）
- 递归
递归函数的参数辅助层级level
每一层的第一个节点，新建这一层级的集合
本层之后的节点都添加到这个集合中
子节点遍历递归，level+1 - 迭代
辅助队列（FIFO）从上往下，从左向右依次入队列，依次出队列
入队列之后，队列中所有元素都处于同一层级，记录这个count，遍历出队列到同一结果集
详细题解：https://www.jianshu.com/p/ca9769cec198
GitHub：https://github.com/huxq-coder/LeetCode
欢迎star
