前言#

遍历树的两个策略

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

准备 TreeNode 构造函数#

1
function TreeNode(val){
2
  this.val = val
3
  this.left = this.right = null
4
}

1. DFS 先序遍历#

反序列化#

1
// 将先序遍历后的字符串 转为二叉树结构
2
var deserialize = (data) => {
3
  const list = data.split(',')       // 转成list数组
4
  return buildTree(list)             // 构建树，dfs的入口
5
}
6

7
var buildTree = (list) => {
8
  let nodeVal = list.shift()
9
  if(nodeVal === 'X') return null
10

11
  let node = new TreeNode(nodeVal)
12
  node.left = buildTree(list)
13
  node.right = buildTree(list)
14
  return node
15
}

序列化#

1
// 将二叉树先序遍历 返回字符串
2
var serialize = (root) => {
3
  if (root == null) return 'X,' // 遇到null节点
4
  const leftSerialized = serialize(root.left)   //左子树的序列化字符串
5
  const rightSerialized = serialize(root.right) //右子树的序列化字符串
6
  return root.val + ',' + leftSerialized + rightSerialized // 根|左|右
7
}

中序遍历可以反序列化吗?#

答案是否定的请看下图

如果增加一个条件，即二叉树的高度平衡，是否可以唯一确定一个二叉树

答案仍然是否定的

后序遍历可以反序列化吗?#

2 BFS#

序列化#

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.join(',')
16
}

反序列化#

1
var deserialize = (data) => {
2
  if(data === 'X') return null
3
  let list = data.split(',')
4
  let root = new TreeNode(list[0])
5

6
  let queue = [root]
7
  let cursor = 1
8
  while(cursor < list.length){
9
    node = queue.shift()
10
    leftVal = list[cursor]
11
    rightVal = list[cursor+1]
12
    cursor += 2
13
    if(leftVal !== 'X'){
14
      let leftNode = new TreeNode(leftVal)
15
      node.left = leftNode
16
      queue.push(leftNode)
17
    }
18
    if(rightVal !== 'X'){
19
      let rightNode = new TreeNode(rightVal)
20
      node.right = rightNode
21
      queue.push(rightNode)
22
    }
23
  }
24
  return root
25
}