二叉树的遍历

二叉树根据遍历的方式，分为深度优先遍历和广度优先遍历

广度优先遍历

广度优先遍历，就是先将一层的树全部遍历完之后，再往下走，在二叉树中便是层序遍历。

深度优先遍历

在二叉树的深度优先遍历中，分为了三种

1. 前序(根-左-右)
2. 中序(左-根-右)
3. 后序(左-右-根)

这里的前中后是根据根节点遍历的先后来命名的。

广度优先遍历

function bfs(tree){
  let queue = [tree]
  while(queue.length){
    let node = queue.shift()
    // 遍历
    console.log(node)
    node.left && queue.push(node.left)
    node.right && queue.push(node.right)
  }
}

深度优先遍历

前序

function dfs_front(node){
  console.log(node.val)
  node.left && dfs_front(node.left)
  node.right && dfs_front(node.right) 
}

中序

function dfs_front(node){
  node.left && dfs_front(node.left)
  console.log(node.val)
  node.right && dfs_front(node.right) 
}

后序

function dfs_front(node){
  node.left && dfs_front(node.left)
  node.right && dfs_front(node.right) 
  console.log(node.val)
}