[数据结构与算法]leetcode 102.二叉树的层序遍历

难度：中等
频率：150
题目：
给你一个二叉树，请你返回其层序遍历得到的节点值（逐层，从左到右访问所有节点）

做这道题 之前先回忆一下数据结构里的 BFS（Breath First Search，广度优先搜索）和DFS（Depth First Search）如何实现遍历。

• DFS[递归方法]

void dfs(TreeNode root)
{
	if(root!=null)
	dfs(root.left);
	dfs(root.right)；
}

• BFS[使用队列数据结构]

void bfs(TreeNode root)
{
  Queue<TreeNode> queue=new ArrayDeque<>();
  queue.add(root);
  while(!queue.isEmpty()){
		TreeNode node = queue.poll();
		if(node.left!=null)
		{
			queue.add(node.left);
		}
		if(node.right!=null)
		{
			queue.add(node.right);
		}
  }
}

总结：BFS用来解决层级遍历问题，而DFS用来解决最短路径问题。

解题方法：BFS变形
解题思路：
1.在常规的BFS遍历中【队列】，加入一个参数，记录这一层的节点数量。
比如一开始root进入的时候，记录数量1。判断一左一右为一次。计次1次遍历，即遍历一棵小树。
然后进入2个，这个时候就会记录2。然后倒计时遍历2次，即遍历两个小树，或者理解为2个root。
2.每一次倒计时用一个arraylist，每次队列出去的数，都放在arraylist里。
3.最后再用一个大的arraylist，把之前每一次的arraylist装起来。

/**
 * 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>> res=new ArrayList<>();
        Queue<TreeNode>queue=new ArrayDeque();
        if(root!=null)
        queue.add(root);
        while(!queue.isEmpty()){
            int n=queue.size();
            List<Integer> arr = new ArrayList();
            for(int i=0;i<n;i++)
            {
                TreeNode node =queue.poll(); 
                arr.add(node.val);
                if(node.left!=null)
                {
                    queue.add(node.left);
                }
                if(node.right!=null)
                {
                    queue.add(node.right);
                }
            }
            res.add(arr);
        }  return res;
    }
  
}

PS:易错点

• 双向队列里面装的是树节点，不是普通类型。
• 一开始的根节点需要判断是否为空。
• list添加的都是值，不是树节点。
• 队列的里节点的数量 是 queue.size()。
• list里套list。二位数组。