数据结构定义

每个节点至多有两个孩子。

 function TreeNode(val, left, right) {
     this.val = (val===undefined ? 0 : val)
     this.left = (left===undefined ? null : left)
     this.right = (right===undefined ? null : right)
 }

binary tree

已上图二叉树为例，遍历顺序分别为：

• BFS: [a,b,c,d,e,f]
• DFS(preOrder): [a, b, d, c, e, f]
• DFS(inOrder): [b, d, a, e, c, f]
• DFS(postOrder): [d, b, e, f, c, a]

BFS（广度优先搜索，又名层次遍历）

BFS依靠队列来实现

递归遍历

function BFS(root){
   let queue = [root];
   recursive(queue);
   function recursive(queue){
     const node = queue.shift();
     if(!node)return;
     console.log(node.val);
     if(root.left)queue.push(node.left);
     if(root.right)queue.push(node.right);
     recursive()
   }
}

非递归遍历

function BFS(root){
   if(!root)return;
   let queue= [root];
   while(queue.length){
       const node = queue.shift();
       console.log(node.val);
       if(node.left)queue.push(node.left);
       if(node.right)queue.push(node.right);
   }
}

DFS（深度优先搜索）

所谓前序，中序，后序中的“序”是针对父节点而言。以先序举例，父节点在前面，则为前序，即NLR(根左右)，那么NRL也是先序吗？根据维基百科的介绍，NRL是reverse preOrder, 因此也是先序。

preOrder(前序)

递归遍历

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

基于stack的非递归遍历

function preOrder(root){
  let stack = [root];
  let result = [];
  
  while(stack.length){
    const top = stack.pop();
    result.push(top.val);
    if(top.right)stack.push(top.right);
    if(top.left)stack.push(top.left);
  }
  return result;
}

inOrder(中序)

递归遍历

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

非递归遍历

function inOrder(node){
  let stack = [];
  let result = [];
  let current = node;
  
  while(current || stack .length){
    while(current){
      stack .push(current)
      current = current.left;
    }
    
    const top = stack .pop();
    result.push(top.val);
    current = top.right;
  }
  return result
}

postOrder(后序)

后序实际上就是中序的颠倒：
中左右 --- reverse ---> 右左中
所以可以把中序的结果倒转一下就得到了中序的遍历结果。

递归遍历

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

非递归遍历

function postOrder(root){
  let stack = [];
  let result = [];
  stack.push(root);
  while(stack.length){
    const top = stack.pop();
    result.push(top.val);
    if(top.left){
      stack.push(top.left);
    }
    if(top.right){
      stack.push(top.right);
    }
  }
  return result.reverse();
}