leetcode 102. 二叉树的层序遍历

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

java 解题思路及代码实现

package com.java.leetcode.tree;

import com.java.leetcode.compent.TreeNode;

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

/**
 * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[9,20],[15,7]]
 * 示例 2：
 *
 * 输入：root = [1]
 * 输出：[[1]]
 * 示例 3：
 *
 * 输入：root = []
 * 输出：[]
 */

public class levelOrder102 {
    /**
     * 思路 层序遍历 即图论中的广度优先遍历，对于层序遍历 不难理解 是一层一层的遍历每一层的所有节点
     * 那么便有 获取一层处理一层 处理完该层  ，然后处理下一层结果
     * 那么处理此类数据就是顺序一层一层处理 和queue 先进先出 的逻辑相同
     * 那么就有 以下思路
     *   处理某一层 节点 记录该节点值 存入 list 中
     *   并将该节点的左右节点填入queue 中，那么 如何判断该层节点是否已经处理完了 就需要有个变量 size 来记录存入对列的节点数
     *   处理该层节点时 size 是否为 0 来判定该层节点有没有处理完成
     * @param root
     * @return
     */
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> list=new ArrayList<>();
            ArrayDeque<TreeNode> que=new ArrayDeque<>();
            if(root==null){
               return list;
            }
            //初始化
            que.offer(root);
            while(!que.isEmpty()){
               // 开始处理节点
                List<Integer> tmp=new ArrayList<>();
                int size= que.size();
                while(size>0){
                    TreeNode node=que.poll();
                    tmp.add(node.getVal());
                    size--;
                    if(node.getLeft()!=null){
                        que.offer(node.getLeft());
                    }
                    if(node.getRight()!=null){
                        que.offer(node.getRight());
                    }
                }
                list.add(tmp);
            }
       return list;
    }
}