二叉树的前序遍历

二叉树的前序遍历：先遍历自身的节点，在遍历左节点，最后遍历右节点

leetcode地址：
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

解法1 递归

let result = []
function treefun(root){
  if(!root)return
  result.push(root.val)
  treefun(root.left)
  treefun(root.right)
}

解法2 迭代

let result = []
function treefun(root){
  let stack = []
  let ptr = root
  stack.push(ptr)
  while(stack.length){
     ptr = stack.pop()
    result.push(ptr.val)
    if(ptr.right)stack.push(ptr.right)
    if(ptr.left) stack.push(ptr.left)
  }
}

解法3 还是迭代解法

遍历到每一个节点，遍历左节点，如果有右节点，将右节点推入，左节点遍历完了，将右节点的数组拿出来遍历

let result = []
function treefun(root){
  let stack = []
  let ptr = root
  while(ptr ){
    result.push(ptr.val)
    // 如果右节点存在，先保存起来，
    if(ptr.right)stack.push(ptr.right)
    // 如果左节点存在，就访问左节点，不存在，就取右节点的数组来访问
    if(ptr.left){
      ptr= ptr.left
    }else {
      ptr= stack.pop()
    }
  }
}