关于二叉树的总结

发表于 | 分类于
关于DFS 和 BFS
为什么前中后序遍历用栈，而层序遍历使用队列 ？

二叉树的前中后序遍历的迭代时，我们用栈来简化操作，因为它们都是DFS的递归结构，也就是从下到上处理，但是我写代码一定是从root节点开始，所以需要栈，而栈正好是先进先出的。这样我才可以把处理root放在最后。

层序遍历是BFS，由上至下。最先入队的root也是我想最先处理的。这就是为什么DFS 使用栈而BFS使用队列的原因。

DFS的算法流程与模板

  1. 首先将根节点放入stack中。

  2. 从stack中取出第一个节点，并检验它是否为目标。如果找到所有的节点，则结束搜寻并回传结果。否则将它某一个尚未检验过的直接子节点加入stack中。

  3. 重复步骤 2。

  4. 如果不存在未检测过的直接子节点。将上一级节点加入stack中。

  5. 重复步骤 2。

  6. 重复步骤 4。

若stack为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

1
2
3
4
5
6
7
8
function dfs(root) {
    if (满足特定条件）{
        // 返回结果 or 退出搜索空间
    }
    for (const child of root.children) {
        dfs(child)
    }
}
BFS 的算法流程与模板

  1. 首先将根节点放入队列中。

  2. 从队列中取出第一个节点，并检验它是否为目标。

  • 如果找到目标，则结束搜索并回传结果。
  • 否则将它所有尚未检验过的直接子节点加入队列中。

  1. 若队列为空，表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。

  2. 重复步骤 2。

1
2
3
4
5
6
7
8
9
function bfs(root) {
  var que = [root]
  while(que.length) {
    var node = que.shift()
     if (node 是我们要找到的)  return node
     node.left && que.push(node.left)
    	node.right && que.push(node.right)
  }
}