102二叉树的层序遍历

//给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
//
// 示例：
//二叉树：[3,9,20,null,null,15,7],
//
// 3
// /
// 9 20
// /
// 15 7
//
// 返回其层次遍历结果：
//
// [
// [3],
// [9,20],
// [15,7]
//]
//
// Related Topics 树 广度优先搜索

• 思路1：BFS，广度优先遍历，1、通过queue记录每一层 2、通过batch process 时间复杂度O（n）
• 思路2：DFS，深度优先遍历，思路是比较清奇的，遍历到不同层次的结点，就加在不同层的数组中 时间复杂度O（n）

这里采用广度优先遍历的第一种 通过queue记录每一层

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
	public List<List<Integer>> levelOrder(TreeNode root) {
		if (root == null) return new ArrayList<>();
		List<List<Integer>> result = new ArrayList<>();
		Queue<TreeNode> queue = new LinkedList();
		queue.add(root);
		while (queue.size() != 0) {
			// 当前层的结点个数
			int current_level_size = queue.size();
			// 存放当前层的遍历结果
			List<Integer> current_level = new ArrayList<>();
			for (int i = 0; i < current_level_size; i++) {
				// 获取左边的结点
				TreeNode node = queue.poll();
				// 遍历
				current_level.add(node.val);
				// 先遍历下层的左边
				if (node.left != null) {
					// 加到queue队列中，便于下次遍历
					queue.add(node.left);
				}
				if (node.right != null) {
					queue.add(node.right);
				}
			}
			result.add(current_level);
		}
		return result;
	}
}