算法-树-深度优先遍历

发表于 更新于

深度优先遍历

前序遍历

二叉树的前序遍历，输出顺序是根节点、左子树、右子树。

遍历过程

image-20210510224549490

上图是一个二叉树，其中前序遍历顺序为（1245367）

image-20210510225200875
  1. 先遍历根节点（1）
  2. 遍历根节点下的左节点（2）
  3. 遍历左节点下的左节点（4），没有子节点，返回上一个节点（2），
  4. 遍历其右节点（5），没有子节点，返回上上一节点（1）
  5. 遍历其右节点（3）
  6. 遍历（3）左节点（6），没有子节点，返回上一节点
  7. 遍历右节点（7），遍历完成

代码

  • 递归
1
2
3
4
5
6
7
8
9
let dfs = function(node){
    if (node === null) return;
    // 输出当前节点的值
    console.log(node.val);
    // 遍历当前节点左节点
    if (node.left) dfs(node.left);
    // 遍历当前节点的右节点
    if(node.right) dfs(node.right);
}
  • 迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var dfs = function (root) {
    if (root === null) return
    
    // 栈，用于回溯
    let stk = [];
    // 先遍历根节点
    let node = root;
    while (node !== null || stk.length !== 0) {

        // 把当前节点的左节点放入stk
        while (node !== null) {
            console.log(node.val);
            stk.push(node);
            node = node.left;
        }

        // 遍历右节点
        if (stk.length !== 0) {
            // 回溯，取出stk中的左节点，遍历右节点
            node = stk.pop();
            node = node.right;
        }
    }
}

中序遍历

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。