树的前中序遍历

前序遍历

前序遍历就是先找到父节点，放入到结果集中，然后是是左节点，最后是右节点。顺序：父 -> 左 -> 右

非递归实现

递归使用了调用栈，可以用栈来模拟递归调用的过程。
栈是先进后出（后入先出），所以将右节点先压入栈中，再把左节点压入栈中，这样在下一轮循环时，先处理左节点，拿到值将其弹出。直到左子树没有子节点，再回过头来处理右子节点。直到栈中数据全部为空为止

function preorderTraversal(root: TreeNode | null): number[] {
  let result: number[] = []
  if(root === null) return result
  let stack: Array<TreeNode> = []
  stack.push(root)   // 根先入栈
  while(stack.length) {
    let node = stack.pop()   // 操作栈最后一项，出栈
    node && result.push(node.val)
    if(node) {
      if(node.right) stack.push(node.right)  // 先压入右节点
      if(node.left) stack.push(node.left)      // 再压入左节点，下一轮先处理这个节点
    }
  }
  return result
};

还有一种看起来比较直观的写法。

思路，不断访问左节点，也就是每个子树的根，将值放入数组中，同时将右子树压入到栈内。
等到左子树访问结束，再从栈中依次取出右子树，进行取值。

function preorderTraversal(root: TreeNode | null): number[] {
  let result: number[] = []
  if(root === null) return result
  let stack: Array<TreeNode> = []

  let p: any = root
  // 根节点先入结果集中，然后不断找左节点
  while(p || stack.length) {
    while(p){
      result.push(p.val)
      if(p.right) stack.push(p.right)
      p = p.left
    }
    p = stack.pop()
  }
  return result
};

中序遍历

取值的顺序：左 -> 父 -> 右

思路：不断把左子树压入栈中，不取值，直到结束；然后从栈中弹出左子树，并取值放入结果数组中，然后再进行有子树的遍历。

function inorderTraversal(root: TreeNode | null): number[] {

  if(root === null) return []

  let stack:Array<any>  = []
  let result: number[] = []
  let p: any = root
  // 依次找到左侧，压入到栈内，然后找右侧
  while(p || stack.length) {
    while(p) {
      stack.push(p)
      p = p.left
    }
    p = stack.pop()
    if(p) result.push(p.val)
    p = p.right
  }
  return result
};

后序遍历

顺序：左 -> 右 -> 父

思路：先不断的的寻找左侧，压入栈中，取出结果放入结果数组中；然后再取右节点，这样最后结果顺序是 父 -> 左 -> 右，最终将结果翻转即可。但这样不能保证是 左 -> 右 -> 父， 所以还需要其他的办法。

function postorderTraversal(root: TreeNode | null): number[] {
  if(root === null) return []
  let stack:Array<any>  = []
  let result: number[] = []
  let p: any = root
  while(p || stack.length) {
    // 依次找右侧
    while(p){
      result.push(p.val)
      stack.push(p)
      p = p.left
    }
    p = stack.pop()
    p = p.right
  }
  return result.reverse()
};

以上为非递归写法，其实处处都参考递归的方式。