二叉树的递归/层序遍历 递归遍历(DFS)

简介: 本文详解二叉树的遍历框架,涵盖递归遍历的固定访问顺序及前、中、后序的本质区别——即代码在递归函数中的位置不同所致。同时深入讲解层序遍历(BFS)的三种实现方式,适用于不同场景,尤其适合求最短路径问题;而DFS则因结构天然适合搜索所有路径。通过实例对比,阐明BFS与DFS的应用偏好及原理依据。

二叉树的遍历框架:

// 基本的二叉树节点

class TreeNode {

int val;

TreeNode left, right;

}


// 二叉树的遍历框架

void traverse(TreeNode root) {

if (root == null) {

return;

}

traverse(root.left);

traverse(root.right);

}

traverse 函数的遍历顺序就是一直往左子节点走,直到遇到空指针不能再走了,才尝试往右子节点走一步;然后再一直尝试往左子节点走,如此循环;如果左右子树都走完了,则返回上一层父节点。其实看代码也能看出来,先递归调用的 root.left,然后才递归调用的 root.right 嘛。

这个递归遍历节点顺序是固定的,务必记住这个顺序,否则你肯定玩不转二叉树结构。

那么有一些数据结构基础的读者肯定要问了:不对呀,只要上过大学的数据结构课程都知道,二叉树有前/中/后序三种遍历,会得到三种不同顺序的结果。为啥你这里说递归遍历节点的顺序是固定的呢?

这个问题很好,我来解答一下。

Important

递归遍历的顺序,即 traverse 函数访问节点的顺序确实是固定的。正如上面那个视频,root 指针在树上移动的顺序是固定的。

但是你在 traverse 函数中不同位置写代码,效果是可以不一样的。前中后序遍历的结果不同,原因是因为你把代码写在了不同位置,所以产生了不同的效果。

比方说,刚进入一个节点的时候,你还对它的子节点一无所知,而当你要离开一个节点的时候,它的所有子节点你都遍历过了。那么在这两种情况下写的代码,肯定是可以有不同的效果的。

你所谓的前中后序遍历,其实就是在上述二叉树遍历框架的不同位置写代码:

// 二叉树的遍历框架

void traverse(TreeNode root) {

   if (root == null) {

       return;

   }

   // 前序位置

   traverse(root.left);

   // 中序位置

   traverse(root.right);

   // 后序位置

}

前序位置的代码会在进入节点时执行;中序位置的代码会在左子树遍历完成后,遍历右子树之前执行;后序位置的代码会在左右子树遍历完成后执行:

层序遍历(BFS)

上面的递归遍历是依赖函数堆栈递归遍历二叉树的,如果把递归函数 traverse 看做一个指针,那么这个指针在二叉树上游走的顺序大概是从最左侧开始,一列一列走到最右侧。
二叉树的层序遍历,顾名思义,就是一层一层地遍历二叉树。这个遍历方式需要借助队列来实现,而且根据不同的需求,主要有三种不同的写法,下面一一列举。

写法一

这是最简单的写法,代码如下:

void levelOrderTraverse(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        TreeNode cur = q.poll();
        // 访问 cur 节点
        System.out.println(cur.val);
        // 把 cur 的左右子节点加入队列
        if (cur.left != null) {
            q.offer(cur.left);
        }
        if (cur.right != null) {
            q.offer(cur.right);
        }
    }
}

cur 变量在树上游走的顺序可以得到层序遍历是一层一层,从左到右的遍历二叉树节点

这种写法的优缺点

这种写法最大的优势就是简单。每次把队头元素拿出来,然后把它的左右子节点加入队列,就完事了。但是这种写法的缺点是,无法知道当前节点在第几层。知道节点的层数是个常见的需求,比方说让你收集每一层的节点,或者计算二叉树的最小深度等等。

所以这种写法虽然简单,但用的不多,下面介绍的写法会更常见一些。

写法二

对上面的解法稍加改造,就得出了下面这种写法:

void levelOrderTraverse(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    // 记录当前遍历到的层数(根节点视为第 1 层)
    int depth = 1;
    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            // 访问 cur 节点,同时知道它所在的层数
            System.out.println("depth = " + depth + ", val = " + cur.val);
            // 把 cur 的左右子节点加入队列
            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
        depth++;
    }
}

注意代码中的内层 for 循环:

int sz = q.size();
for (int i = 0; i < sz; i++) {
    ...
}

这个变量 i 记录的是节点 cur 是当前层的第几个,大部分算法题中都不会用到这个变量,所以你完全可以改用下面的写法:

int sz = q.size();
while (sz-- > 0) {
    ...
}

这个属于细节问题,按照自己的喜好来就行。

但是注意队列的长度 sz 一定要在循环开始前保存下来,因为在循环过程中队列的长度是会变化的,不能直接用 q.size() 作为循环条件。

写法三

既然写法二是最常见的,为啥还有个写法三呢?因为要给后面的进阶内容做铺垫。

现在我们只是在探讨二叉树的层序遍历,但是二叉树的层序遍历可以衍生出 多叉树的层序遍历,图的 BFS 遍历,以及经典的 BFS 暴力穷举算法框架,所以这里要拓展延伸一下。

回顾写法二,我们每向下遍历一层,就给 depth 加 1,可以理解为每条树枝的权重是 1,二叉树中每个节点的深度,其实就是从根节点到这个节点的路径权重和,且同一层的所有节点,路径权重和都是相同的。

那么假设,如果每条树枝的权重和可以是任意值,现在让你层序遍历整棵树,打印每个节点的路径权重和,你会怎么做?这样的话,同一层节点的路径权重和就不一定相同了,写法二这样只维护一个 depth 变量就无法满足需求了。

写法三就是为了解决这个问题,在写法一的基础上添加一个 State 类,让每个节点自己负责维护自己的路径权重和,代码如下:

class State {
    TreeNode node;
    int depth;
    State(TreeNode node, int depth) {
        this.node = node;
        this.depth = depth;
    }
}
void levelOrderTraverse(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<State> q = new LinkedList<>();
    // 根节点的路径权重和是 1
    q.offer(new State(root, 1));
    while (!q.isEmpty()) {
        State cur = q.poll();
        // 访问 cur 节点,同时知道它的路径权重和
        System.out.println("depth = " + cur.depth + ", val = " + cur.node.val);
        // 把 cur 的左右子节点加入队列
        if (cur.node.left != null) {
            q.offer(new State(cur.node.left, cur.depth + 1));
        }
        if (cur.node.right != null) {
            q.offer(new State(cur.node.right, cur.depth + 1));
        }
    }
}

这样每个节点都有了自己的 depth 变量,是最灵活的,可以满足所有 BFS 算法的需求。但是由于要额外定义一个 State 类比较麻烦,所以非必要的话,用写法二就够了。

为什么 BFS 常用来寻找最短路径

来看力扣第 111 题「二叉树的最小深度」:

111. 二叉树的最小深度 | 力扣 | LeetCode |  

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明:叶子节点是指没有子节点的节点。

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:2

示例 2:

输入:root = [2,null,3,null,4,null,5,null,6]
输出:5

提示:

  • 树中节点数的范围在 [0, 105] 内
  • -1000 <= Node.val <= 1000

二叉树的最小深度即「根节点到最近的叶子节点的距离」,所以这道题本质上就是让你求最短距离。

DFS 递归遍历和 BFS 层序遍历都可以解决这道题,先看 DFS 递归遍历的解法:

class Solution {
    // 记录最小深度(根节点到最近的叶子节点的距离)
    private int minDepth = Integer.MAX_VALUE;
    // 记录当前遍历到的节点深度
    private int currentDepth = 0;
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 从根节点开始 DFS 遍历
        traverse(root);
        return minDepth;
    }
    private void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // 前序位置进入节点时增加当前深度
        currentDepth++;
        // 如果当前节点是叶子节点,更新最小深度
        if (root.left == null && root.right == null) {
            minDepth = Math.min(minDepth, currentDepth);
        }
        traverse(root.left);
        traverse(root.right);
        // 后序位置离开节点时减少当前深度
        currentDepth--;
    }
}

每当遍历到一条树枝的叶子节点,就会更新最小深度,当遍历完整棵树后,就能算出整棵树的最小深度。你能不能在不遍历完整棵树的情况下,提前结束算法?不可以,因为你必须确切的知道每条树枝的深度(根节点到叶子节点的距离),才能找到最小的那个。

下面来看 BFS 层序遍历的解法。按照 BFS 从上到下逐层遍历二叉树的特点,当遍历到第一个叶子节点时,就能得到最小深度:

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        // root 本身就是一层,depth 初始化为 1
        int depth = 1;
        while (!q.isEmpty()) {
            int sz = q.size();
            // 遍历当前层的节点
            for (int i = 0; i < sz; i++) {
                TreeNode cur = q.poll();
                // 判断是否到达叶子结点
                if (cur.left == null && cur.right == null)
                    return depth;
                // 将下一层节点加入队列
                if (cur.left != null)
                    q.offer(cur.left);
                if (cur.right != null)
                    q.offer(cur.right);
            }
            // 这里增加步数
            depth++;
        }
        return depth;
    }
}

由于 BFS 逐层遍历的逻辑,第一次遇到目标节点时,所经过的路径就是最短路径,算法可能并不需要遍历完所有节点就能提前结束。DFS 遍历当然也可以用来寻找最短路径,但必须遍历完所有节点才能得到最短路径。从时间复杂度的角度来看,两种算法在最坏情况下都会遍历所有节点,时间复杂度都是 O(N)O(N),但在一般情况下,显然 BFS 算法的实际效率会更高。所以在寻找最短路径的问题中,BFS 算法是首选。

为什么 DFS 常用来寻找所有路径

在寻找所有路径的问题中,你会发现 DFS 算法用的比较多,BFS 算法似乎用的不多。

理论上两种遍历算法都是可以的,只不过 BFS 算法寻找所有路径的代码比较复杂,DFS 算法代码比较简洁。你想啊,就以二叉树为例,如果要用 BFS 算法来寻找所有路径(根节点到每个叶子节点都是一条路径),队列里面就不能只放节点了,而需要使用第三种写法,新建一个 State 类,把当前节点以及到达当前节点的路径都存进去,这样才能正确维护每个节点的路径,最终计算出所有路径。

而使用 DFS 算法就简单了,它本就是一条树枝一条树枝从左往右遍历的,每条树枝就是一条路径,所以 DFS 算法天然适合寻找所有路径。最后结合代码和可视化面板讲解一下,先看 DFS 算法的可视化面板,你可以多次点击 if (root === null) 这部分代码,观察 DFS 算法遍历所有节点并收集根节点到叶子节点的所有路径:

综上,DFS 算法在寻找所有路径的问题中更常用,而 BFS 算法在寻找最短路径的问题中更常用。


相关文章
|
存储 算法
树(Tree) - 概念与基础
树(Tree) - 概念与基础
|
存储 安全 编译器
C# 11.0中的泛型属性:类型安全的新篇章
【1月更文挑战第23天】C# 11.0引入了泛型属性的概念,这一新特性为开发者提供了更高级别的类型安全性和灵活性。本文将详细探讨C# 11.0中泛型属性的工作原理、使用场景以及它们对现有编程模式的改进。通过深入了解泛型属性,开发者将能够编写更加健壮、可维护的代码,并充分利用C#语言的最新发展。
|
1月前
|
Java Windows
【保姆级】Java配置环境变量图文教程,超级详细
本文详细介绍了Windows 10系统下JDK环境变量配置的完整步骤:包括设置JAVA_HOME变量、将%JAVA_HOME%\bin添加至Path路径,以及通过cmd执行java -version命令验证配置是否成功,图文并茂,操作清晰易懂。
|
5月前
|
缓存 人工智能 运维
GLM 5.2自托管全流程实战:硬件选型、vLLM/SGLang部署与成本盈亏测算
2026年智谱发布GLM 5.2超大混合专家模型,区别于以往仅开放API的闭源大模型,该模型权重以MIT开源协议对外发布,企业与开发者可完整下载、本地审计、私有化部署,实现数据不出环境、自定义微调、自主调度推理资源。GLM 5.2拥有753B总参数,原生支持百万级上下文窗口,在代码生成、长文档推理、数学逻辑等多项基准测试中对标国际顶尖商用模型,是首款可完整自托管的前沿代码向大模型。
2605 0
|
9月前
|
存储 人工智能 搜索推荐
AI Agent 记忆系统:从短期到长期的技术架构与实践
本文系统阐述AI Agent记忆系统的核心技术:短期记忆(会话级上下文管理)与长期记忆(跨会话知识沉淀)。涵盖上下文工程策略(压缩、卸载、隔离)、Record/Retrieve架构、主流框架(ADK/LangChain/AgentScope)实现差异,及Mem0等开源方案集成,并探讨MaaS、多模态记忆等前沿趋势。(239字)
13532 4
AI Agent 记忆系统:从短期到长期的技术架构与实践
|
11月前
|
存储 缓存 算法
学习数据结构和算法的框架思维
本文系统梳理数据结构与算法核心思想:所有数据结构本质为数组或链表的变形,基本操作均为遍历与访问;算法本质是穷举,关键在于“无遗漏”和“无冗余”。掌握框架思维,方能以不变应万变,高效刷题。
学习数据结构和算法的框架思维
|
开发工具 git