二叉树的遍历按照顺序有四种形式：

  1. 前序遍历（根-左-右）
  2. 中序遍历（左-根-右）
  3. 后序遍历（左-右-根）
  4. 层次遍历

其中前三种遍历都可以通过递归实现，还可以通过迭代实现，实现方法要牢记
而层次遍历需要通过BFS实现，详见后面章节 DFS 与 BFS

递归实现二叉树遍历

将下面二叉树前序遍历、中序遍历、后续遍历的结果放到一个数组里返回

image.png
递归遍历首先应该明确两样东西：

  1. 递归式
  2. 递归边界

注：在递归函数中，递归边界判断应该放到最前面，在边界内的时候才会执行递归式，否则退出函数

  1. const root = {
  2.   val:'A',
  3.   left:{
  4.     val: 'B',
  5.     left:{
  6.       val: 'D',
  7.     },
  8.     right:{
  9.       val:'E'
  10.     }
  11.   },
  12.   right:{
  13.     val: 'C',
  14.     right: {
  15.       val: 'F'
  16.     }
  17.   }
  18. }

前序遍历（LeetCode 144）

  1. function preorder(root) {
  2.   const res = []
  3.   DFS(root)
  4.   function DFS(root){ // 深度优先搜索
  5.     // 递归边界
  6.     if(!root) return 
  7.     res.push(root.val)
  8.     // 递归遍历左子树
  9.     DFS(root.left)
  10.     // 递归遍历右子树
  11.     DFS(root.right)
  12.   }
  13.   return res
  14. }
  16. console.log(preorder(root))
  17. // [ 'A', 'B', 'D', 'E', 'C', 'F' ]

后序遍历（LeetCode 145）

  1. function postorder(root) { // 把结果放到一个数组里
  2.   const res = []
  3.   DFS(root)
  4.   function DFS(root){
  5.     if(!root) return 
  6.     DFS(root.left)
  7.     DFS(root.right)
  8.     res.push(root.val)
  9.   }
  10.   return res
  11. }
  13. console.log(postorder(root))
  14. // [ 'D', 'E', 'B', 'F', 'C', 'A' ]

中序遍历（LeetCode 94）

function inorder(root) { // 把结果放到一个数组里
  const res = []
  DFS(root)
  function DFS(root){
    if(!root) return 
    DFS(root.left)
    res.push(root.val)
    DFS(root.right)
  }
  return res
}

console.log(inorder(root))
// [ 'D', 'B', 'E', 'A', 'C', 'F' ]

迭代实现二叉树遍历

二叉树的前序遍历、中序遍历和后序遍历用递归的方法实现简单清晰，
但是也可以通过迭代（循环）实现，需要一个栈结构来模拟遍历的规则

前序遍历（LeetCode 144）

  1. 首先根结点入栈
  2. 取出栈顶元素，值push 进结果数组res
  3. 若根结点有右子树，将右子树结点入栈
  4. 若根结点有左子树，将左子树结点入栈

左子树后入栈，就会先出栈，符合前序遍历的顺序，重复2，3，4 直到栈为空

var preorderTraversal = function(root) { // 迭代：辅助栈
  const res = []
  const stack = []
  root && stack.push(root)
  while(stack.length){
    const top = stack.pop()
    res.push(top.val)
    top.right && stack.push(top.right)
    top.left && stack.push(top.left)
  }
  return res
};

后序遍历（LeetCode 145）

后序遍历与前序遍历方法类似，由于我们只能从根结点开始操作，所以我们把遍历顺序左-右-根反转变成根-右-左，然后结果数组 res 通过 unshift 从后往前更新，这样结果符合后续遍历的顺序

var postorderTraversal = function(root) { // res: 先序遍历从前往后，后序遍历从后往前
  const res = [] 
  const stack = []
  root && stack.push(root)
  while(stack.length){
    const top = stack.pop()
    res.unshift(top.val) // 从后往前更新res
    top.left && stack.push(top.left)
    top.right && stack.push(top.right)
  }
  return res
};

中序遍历（LeetCode 94）

中序遍历左-根-右的遍历顺序，根结点在中间，而上面前序遍历和后序遍历的方法都是先从根结点开始，
所以中序遍历无法使用这种方法。
中序遍历要从根结点开始一直访问到左边的子结点，在这个过程中记录经过的结点（入栈），等到最左边子结点出栈后可以回溯到它的父节点，这就可以访问左节点的兄弟右节点了

var inorderTraversal = function(root) { // 迭代
  const stack = [] // 辅助栈
  const res = []
  let cur = root
  while(cur || stack.length){
    while(cur){
      stack.push(cur)
      cur = cur.left
    }
    cur = cur ||  stack.pop()
    res.push(cur.val)
    cur = cur.right
  }
  return res
}