二叉树的先序，中序，后序遍历

先序遍历表示先访问根节点，然后访问左节点，最后访问右节点。

中序遍历表示先访问左节点，然后访问根节点，最后访问右节点。

后序遍历表示先访问左节点，然后访问右节点，最后访问根节点。

递归实现

递归实现相当简单，代码如下

function TreeNode(val) {
  this.val = val
  this.left = this.right = null
}
var traversal = function(root) {
  if (root) {
    // 先序
    console.log(root)
    traversal(root.left)
    // 中序
    // console.log(root);
    traversal(root.right)
    // 后序
    // console.log(root);
  }
}

对于递归的实现来说，只需要理解每个节点都会被访问三次就明白为什么这样实现了。

非递归实现

非递归实现使用了栈的结构，通过栈的先进后出模拟递归实现。

以下是先序遍历代码实现

function pre(root) {
  if (root) {
    let stack = []
    // 先将根节点 push
    stack.push(root)
    // 判断栈中是否为空
    while (stack.length > 0) {
      // 弹出栈顶元素
      root = stack.pop()
      console.log(root)
      // 因为先序遍历是先左后右，栈是先进后出结构
      // 所以先 push 右边再 push 左边
      if (root.right) {
        stack.push(root.right)
      }
      if (root.left) {
        stack.push(root.left)
      }
    }
  }
}

以下是中序遍历代码实现

function mid(root) {
  if (root) {
    let stack = []
    // 中序遍历是先左再根最后右
    // 所以首先应该先把最左边节点遍历到底依次 push 进栈
    // 当左边没有节点时，就打印栈顶元素，然后寻找右节点
    // 对于最左边的叶节点来说，可以把它看成是两个 null 节点的父节点
    // 左边打印不出东西就把父节点拿出来打印，然后再看右节点
    while (stack.length > 0 || root) {
      if (root) {
        stack.push(root)
        root = root.left
      } else {
        root = stack.pop()
        console.log(root)
        root = root.right
      }
    }
  }
}

以下是后序遍历代码实现，该代码使用了两个栈来实现遍历，相比一个栈的遍历来说要容易理解很多

function pos(root) {
  if (root) {
    let stack1 = []
    let stack2 = []
    // 后序遍历是先左再右最后根
    // 所以对于一个栈来说，应该先 push 根节点
    // 然后 push 右节点，最后 push 左节点
    stack1.push(root)
    while (stack1.length > 0) {
      root = stack1.pop()
      stack2.push(root)
      if (root.left) {
        stack1.push(root.left)
      }
      if (root.right) {
        stack1.push(root.right)
      }
    }
    while (stack2.length > 0) {
      console.log(s2.pop())
    }
  }
}