2.二叉树的先中序遍历

1.先序遍历(中左右)

1. 先访问根节点
2. 对根节点的左子树进行先序遍历

3. 对根节点的右子树进行先序遍历

   1.递归法：

   function preOrder(root) {
   if (!root) return
   console.log(root.val);
   preOrder(root.left)
   preOrder(root.right)
   }

   2.栈方法模拟递归

   function preOrder(root) {
   let stack = [root]
   // 先序：中 左 右
   while(stack.length) {
    let node = stack.pop()
    console.log(node.val);
    // 先 push 进 right 是为了先 pop 出left
    // 操作的是 pop 出来的顺序
    node.right && stack.push(node.right)
    node.left && stack.push(node.left)
   }
   }

   2.中序遍历(左中右)

4. 先访问左子节点，对左子节点进行中序遍历

5. 再访问根节点

6. 再访问右子节点，对右子节点进行中序遍历

   1.递归法

   const inorder = root => {
   if (!root) return
   inorder(root.left)
   console.log(root.val);
   inorder(root.right)
   }

   2.迭代法，配合 stack控制任务队列

   var inorderTraversal = function(root) {
   let list = [] // 存放中序遍历顺序
   let stack = [] // 栈控制任务堆栈，模拟递归
   let cur = root // 当前任务指向 root
   while(cur || stack.length) { // 如果存在当前任务，或者任务堆栈种存在任务
    if (cur) {
      // 如果存在当前任务，则往任务堆栈中 push 任务
      stack.push(cur)
      cur = cur.left // 通过 while 循环，将 root 的所有左子节点都先 push 到stack 中
    } else {
      cur = stack.pop() // 如果当前指向节点不存在了，说明左子节点到底了，则从任务堆栈中取出最新push进去的，也就是最底层的 left 节点
      list.push(cur.val)
      cur = cur.right // 关键点：left 都循环完了之后，将当前节点改为 最底层的 left节点的 right，继续循环
    }
   }
   return list
   };

   3.后序遍历(左右根)

7. 先访问左子节点，进行后序遍历

8. 再访问右子节点，对右子节点进行后序遍历
9. 再访问根节点

1.递归版

function nextOrder(node, arr) {
  if (!node) return
  nextOrder(node.left, arr)
  nextOrder(node.right, arr)
  arr.push(node.val)
}

2.堆栈控制法

var postorderTraversal = function(root) {
  let stack = [root] // 任务堆栈，push的顺序与执行的顺序正好相反
  // 只用一个 stack 会变成广度优先遍历
  // 这里再用一个 stack 控制 左右中的任务堆栈
  let outputstack = []
  while(stack.length) {
    let node = stack.pop() // 操作的节点
    outputstack.push(node) // 先往 outputstack push 中 node
    node.left && stack.push(node.left) // 再往 stack 中 push left node
    node.right && stack.push(node.right) // 再往 stack 中 push right node
    // 这样 stack 下一轮 pop 出来的时候就是 right left，再进入  outputstack 就是 right left
  }
  while(outputstack.length) {
    let node = outputstack.pop()
    console.log(node.val);
  }
};