第四阶段算法学习总结

脑图：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