【算法分析与设计】二叉树的层序遍历

       📝个人主页：五敷有你      
 🔥系列专栏：算法分析与设计
⛺️稳中求进，晒太阳

题目

        给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例

示例 1：

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

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

 思路(类似于广度优先遍历)

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

• 首先根元素入队
• 当队列不为空的时候
  • 求当前队列的长度 
  • 依次从队列中取 si个元素进行拓展，然后进入下一次迭代

它和普通广度优先搜索的区别在于，普通广度优先搜索每次只取一个元素拓展，而这里每次取 si 个元素.在上述过程中，第i次迭代就得到了二叉树的第i层的si个元素

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

        初始化：i=1的时候，队列中只有root

        开始遍历

        取出队列中队头的值，然后遍历出它的所有子节点，然后装入队列，之后一直到这一层的结束为止。然后将所有的值装入集合，集合装入大集合。

算法分析与设计

1. 初始化：

   • 初始化一个空的结果列表 ret。
   • 初始化一个队列 queue，将根节点入队。

2. 循环遍历：

   • 使用 while 循环，条件为队列非空。
   • 在循环内部，初始化当前层的列表 level 和当前层的节点数 currentLevelSize。
   • 使用内层循环处理当前层的节点：
     • 出队一个节点，将其值加入 level 列表。
     • 如果有左子节点，将左子节点入队。
     • 如果有右子节点，将右子节点入队。
   • 将当前层的列表 level 添加到结果列表 ret 中。

3. 返回结果：

   • 返回最终的结果列表 ret。

代码实现

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);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 0; i < currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        
        return ret;
    }
}

运行结果

时间复杂度 O(n^2)，其中 N 为树中节点的数量。每个节点都会被访问一次。

空间复杂度O(M)，其中 M 为每层最大的节点数。在最坏情况下，队列的大小会达到树的最底层的节点数。

 随笔：再写这个的时候，有些api不会些，虽然直到思想有思路，但是api也是很重要的。再次我总结了LinkList的api