前言

遍历树的两个策略

DFS 分为先序遍历中序遍历后序遍历
BFS 可以按照层次的顺序从上到下遍历所有的节点

构造一颗二叉树

const node = (value,left,right)=>{
  return {
    value,
    left,
    right
  }
}

const binaryTree = 
  node("A",
    node("B",node("D")),
    node("C",
      node("E",undefined,node("G")),
      node("F",node("H"),node("J"))
    )
  )

1. DFS 先序遍历

利用递归先序遍历

let resultFirst = []
const traverseRootFirst = (bTree) => {
  if(!bTree) { return}
  resultFirst.push(bTree.value)
  traverseRootFirst(bTree.left)
  traverseRootFirst(bTree.right)
}
traverseRootFirst(binaryTree)
console.log('先序遍历')
console.log(resultFirst)  // ["A", "B", "D", "C", "E", "G", "F", "H", "J"]

不利用递归先序遍历

自己维护一个栈当前节点指向根节点

如果当前节点不为空就将当前节点入栈并push到结果数组中并让当前节点指向该节点的左节点
如果当前节点为空就从栈中pop一个节点并让当前节点指向pop出节点的右节点

如果栈不为空或者当前节点不为空重复以上步骤

let resultFirst2 = []
const traverseRootFirst2 = (bTree) => {
  const stack = []
  let current = bTree
  while(stack.length || current){
    if(current){
      resultFirst2.push(current.value)
      stack.push(current)
      current = current.left
    }else{
      current = stack.pop()
      current = current.right
    }
  }
}
traverseRootFirst2(binaryTree)
console.log('\n 不利用递归先序遍历')
console.log(resultFirst2)  // ["A", "B", "D", "C", "E", "G", "F", "H", "J"]

2 DFS 中序遍历

递归

let resultMiddle = []
const traverseRootMiddle = (bTree) => {
  if(!bTree) { return }
  traverseRootMiddle(bTree.left)
  resultMiddle.push(bTree.value)
  traverseRootMiddle(bTree.right)
}
traverseRootMiddle(binaryTree)
console.log('中序遍历')
console.log(resultMiddle)   // ["D", "B", "A", "E", "G", "C", "H", "F", "J"]

不利用递归

自己维护一个栈当前节点指向根节点

如果当前节点不为空就让当前节点指向该节点的左节点
如果当前节点为空就从栈中pop一个节点并将该节点push到结果数组中并将当前节点指向该节点的右节点

如果栈不为空或者当前节点不为空重复以上步骤

与先序遍历唯一不同的就是什么时候放入结果数组

let resultMiddle2 = []
const traverSeRootMiddle2 = (bTree) => {
  const stack = []
  let current = bTree
  while(stack.length || current){
    if(current){
      stack.push(current)
      current = current.left
    }else{
      current = stack.pop()
      resultMiddle2.push(current.value)
      current = current.right
    }
  }
}
traverSeRootMiddle2(binaryTree)
console.log('\n 不利用递归中序遍历')
console.log(resultMiddle2)  // ["D", "B", "A", "E", "G", "C", "H", "F", "J"]

3 DFS 后续遍历

递归

let resultLast = []
const traverseRootLast = (bTree) => {
  if(!bTree) { return }
  traverseRootLast(bTree.left)
  traverseRootLast(bTree.right)
  resultLast.push(bTree.value)
}
traverseRootLast(binaryTree)
console.log('后序遍历')
console.log(resultLast)  // ["D", "B", "G", "E", "H", "J", "F", "C", "A"]

4 BFS

维护一个队列将根节点放入队列中

从队列中取出一个节点node
如果node节点为空的话就将当前的左右节点先后放入队列中
如果当前节点为空队列中push null

如果队列部位空重复以上步骤直到队列中的节点全部被取出遍历完成

var serialize = (root) => {
  let queue = [root]
  let res = []

  while(queue.length){
    let node = queue.shift()
    if(node){
      res.push(node.val)
      queue.push(node.left)
      queue.push(node.right)
    }else{
      res.push('X')
    }
  }
  return res
}