坚持刷题 | 二叉树的层序遍历

发布时间:2024年01月18日

坚持刷题,老年痴呆追不上我,今天刷:二叉树的层序遍历

题目

102二叉树的层序遍历
在这里插入图片描述

考察点

  • 数据结构基础: 能够正确地使用二叉树数据结构,并了解二叉树的基本性质。
  • 编程基础: 能够熟练使用Java编程语言,实现基本的数据结构和算法。
  • 树的遍历算法: 理解并能够正确实现二叉树的层序遍历算法。层序遍历是一种广度优先搜索(BFS)的应用,通常使用队列来实现。

代码实现

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTreeLevelOrderTraversal {
    public static List<List<Integer>> levelOrderTraversal(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> levelNodes = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                levelNodes.add(node.val);

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            result.add(levelNodes);
        }

        return result;
    }

    public static void main(String[] args) {
        // 构建一个二叉树用于测试
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        List<List<Integer>> traversalResult = levelOrderTraversal(root);

        System.out.println("层序遍历结果:");
        System.out.println(traversalResult);
    }
}

实现总结

  • levelOrderTraversal方法返回一个List<List<Integer>>,其中每个内部的List表示一层的节点值
  • 循环过程中,使用了一个内部循环来遍历当前层次的所有节点,并将其值加入到levelNodes
  • 最后将levelNodes加入到结果集合result中
  • 时间复杂度:O(n),n为节点的个数。在整个实现过程中,每个结点都会被访问一次,然后针对每个结点会分别进/出队列一次,为常数时间。设 n 为二叉树的节点数,h 为二叉树的高度,在最差情况下,当二叉树是一条链的时候,h 等于 n。
  • 可能的扩展问题:
    • 如何修改代码以实现Zigzag(蛇形)形式的层序遍历,即交替从左到右和从右到左遍历每一层?
    • 是否可以使用递归方式实现二叉树的层序遍历?如果可以,怎么做?
    • 是否有方法减少空间使用,例如不使用额外的数据结构(队列)?
    • 如何检查二叉树是否是对称的?能否通过层序遍历实现?
    • 如果每个节点除了值之外还包含其他信息,如何适应这种情况?
    • 除了层序遍历,还可以被问及其他遍历方式,比如先序遍历、中序遍历和后序遍历的实现,以及它们的应用。
    • 你的代码的时间复杂度是多少?有没有可能进一步优化?

这些扩展问题会在后续的刷题中逐一解决

文章来源:https://blog.csdn.net/weixin_44435110/article/details/135662290
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。