二叉树层级遍历(深度优先、广度优先算法)

这篇具有很好参考价值的文章主要介绍了二叉树层级遍历(深度优先、广度优先算法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

中等难度

方法一:广度优先搜索

思路和算法

我们可以用广度优先搜索解决这个问题。

我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态,它表示某个节点和它所在的层数,每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类,分类的时候我们可以利用哈希表,维护一个以 level 为键,对应节点值组成的数组为值,广度优先搜索结束以后按键 level 从小到大取出所有值,组成答案返回即可。

考虑如何优化空间开销:如何不用哈希映射,并且只用一个变量 node 表示状态,实现这个功能呢?

我们可以用一种巧妙的方法修改广度优先搜索:

首先根元素入队
当队列不为空的时候
求当前队列的长度 s i

依次从队列中取 s i

个元素进行拓展,然后进入下一次迭代
它和普通广度优先搜索的区别在于,普通广度优先搜索每次只取一个元素拓展,而这里每次取 s
i

个元素。在上述过程中的第 i 次迭代就得到了二叉树的第 i 层的 s i
​ 个元素。

为什么这么做是对的呢?我们观察这个算法,可以归纳出这样的循环不变式:第 i 次迭代前,队列中的所有元素就是第 i 层的所有元素,并且按照从左向右的顺序排列。证明它的三条性质(你也可以把它理解成数学归纳法):

初始化:i=1 的时候,队列里面只有 root,是唯一的层数为 1 的元素,因为只有一个元素,所以也显然满足「从左向右排列」;
保持:如果 i=k 时性质成立,即第 k 轮中出队 s
k

的元素是第 k 层的所有元素,并且顺序从左到右。因为对树进行广度优先搜索的时候由低 k 层的点拓展出的点一定也只能是 k+1 层的点,并且 k+1 层的点只能由第 k 层的点拓展到,所以由这 s
k

个点能拓展到下一层所有的 s
k+1

个点。又因为队列的先进先出(FIFO)特性,既然第 k 层的点的出队顺序是从左向右,那么第 k+1 层也一定是从左向右。至此,我们已经可以通过数学归纳法证明循环不变式的正确性。
终止:因为该循环不变式是正确的,所以按照这个方法迭代之后每次迭代得到的也就是当前层的层次遍历结果。至此,我们证明了算法是正确的。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) { // 如果树为空则直接返回空
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root); //将树root插入队列中
        while (!queue.isEmpty()) { //循环遍历队列`````
            List<Integer> level = new ArrayList<>();
            int currentLevelSize = queue.size();
            for (int i = 0; i < currentLevelSize; ++i) {
                TreeNode node = queue.poll();//取出队列头部的节点
                level.add(node.val);//并将其赋值给 node 变量,以便对该节点执行操作
                if(node.left !=null){
                    queue.offer(node.left);
                }
                if(node.right !=null){
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        return ret;
    }
}

这段代码是用于生成二叉树的层次遍历结果,返回一个二维列表 ret,其中每个子列表表示二叉树的一层节点值。

这里使用了队列(Queue)来辅助实现层次遍历的思路。具体的思路如下:

首先初始化一个空的二维列表 ret,用于存储最终的层次遍历结果。
如果二叉树的根节点 root 为空,则直接返回空的结果列表 ret。
创建一个队列 queue,并将根节点 root 加入队列中。
进入循环,只要队列不为空,就继续执行以下ceng步骤:
创建一个空的列表 level,用于存储当前层的节点值。
获取当前层的节点数 currentLevelSize,即队列的当前大小。
使用一个循环遍历当前层的节点,重复 currentLevelSize 次:
从队列中取出一个节点 node。
将节点 node 的值添加到当前层的列表 level 中。
如果节点 node 的左子节点不为空,则将左子节点加入队列中。
如果节点 node 的右子节点不为空,则将右子节点加入队列中。
将当前层的列表 level 添加到结果列表 ret 中。
循环结束后,所有层次遍历的结果已经存储在列表 ret 中,将其返回作为最终结果。
总结来说,该算法通过队列实现了广度优先搜索(BFS)的层次遍历。从根节点开始,依次处理每一层的节点,并将它们的值添加到结果列表中。同时,将下一层的节点加入到队列中,以便继续遍历。最后,返回得到的二维列表 ret。

复杂度分析

记树上所有节点的个数为 n。

时间复杂度:每个点进队出队各一次,故渐进时间复杂度为 O(n)。
空间复杂度:队列中元素的个数不超过 n 个,故渐进空间复杂度为 O(n)。文章来源地址https://www.toymoban.com/news/detail-704064.html

到了这里,关于二叉树层级遍历(深度优先、广度优先算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包