
脑图: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
网友评论