前言#

遍历树的两个策略

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

构造一颗二叉树#

1
const node = (value,left,right)=>{
2
  return {
3
    value,
4
    left,
5
    right
6
  }
7
}
8

9
const binaryTree =
10
  node("A",
11
    node("B",node("D")),
12
    node("C",
13
      node("E",undefined,node("G")),
14
      node("F",node("H"),node("J"))
15
    )
16
  )

遍历二叉树

1. DFS 先序遍历#

利用递归先序遍历#

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

不利用递归先序遍历#

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

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

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

1
let resultFirst2 = []
2
const traverseRootFirst2 = (bTree) => {
3
  const stack = []
4
  let current = bTree
5
  while(stack.length || current){
6
    if(current){
7
      resultFirst2.push(current.value)
8
      stack.push(current)
9
      current = current.left
10
    }else{
11
      current = stack.pop()
12
      current = current.right
13
    }
14
  }
15
}
16
traverseRootFirst2(binaryTree)
17
console.log('\n 不利用递归先序遍历')
18
console.log(resultFirst2)  // ["A", "B", "D", "C", "E", "G", "F", "H", "J"]

2 DFS 中序遍历#

递归#

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

不利用递归#

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

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

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

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

1
let resultMiddle2 = []
2
const traverSeRootMiddle2 = (bTree) => {
3
  const stack = []
4
  let current = bTree
5
  while(stack.length || current){
6
    if(current){
7
      stack.push(current)
8
      current = current.left
9
    }else{
10
      current = stack.pop()
11
      resultMiddle2.push(current.value)
12
      current = current.right
13
    }
14
  }
15
}
16
traverSeRootMiddle2(binaryTree)
17
console.log('\n 不利用递归中序遍历')
18
console.log(resultMiddle2)  // ["D", "B", "A", "E", "G", "C", "H", "F", "J"]

3 DFS 后续遍历#

递归#

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

4 BFS#

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

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

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

1
var serialize = (root) => {
2
  let queue = [root]
3
  let res = []
4

5
  while(queue.length){
6
    let node = queue.shift()
7
    if(node){
8
      res.push(node.val)
9
      queue.push(node.left)
10
      queue.push(node.right)
11
    }else{
12
      res.push('X')
13
    }
14
  }
15
  return res
16
}