【LeetCode热题100】--102.二叉树的层序遍历-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode热题100】--102.二叉树的层序遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

102.二叉树的层序遍历

【LeetCode热题100】--102.二叉树的层序遍历,# 二叉树,leetcode,算法

广度优先搜索：

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

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

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

首先根节点入队
当队列不为空时：
- 求当前队列的长度 $s_i$
- 依次从队列中取 $s_i$ 个元素进行拓展，然后进入下一次迭代

它和普通广度优先搜索的区别在于：普通广度优先搜索每次只取一个元素拓展，而这里每次取 $s_i$ 个元素文章来源地址https://www.toymoban.com/news/detail-729050.html

/**
 * 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>> ans = new ArrayList<List<Integer>>();
        if(root == null){
            return ans;
        } 
        //队列是先进先出
        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 = 1;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);
                }
            }
            ans.add(level);
        }
        return ans;
    }
}