题目
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
解法思路（一）
- 二叉树的层序遍历是需要借助队列的；
- 如果只是遍历的话，是很基础的操作，但题目对遍历结果的返回格式有要求，
List<List<Integer>>，即结果中要表示出每个节点是在哪一层的； - 这就需要对二叉树中的节点所在的层进行记录，具体做法是将节点和它所在的层包装成一个
Pair，进出队列的都是Pair，每次遍历到哪个节点，就把该节点的值放进其层数对应的线性表中；
解法实现（一）
时间复杂度
- O(n)，n为树的节点个数；
空间复杂度
- O(n)，二叉树是有可能退化成链表的，在这种情况下，h = n；
关键字
二叉树 层序遍历 队列 二维线性表
实现细节
- 在从队列中取出一个节点时，要看一下在返回结果
res中是否有该节点的层数所对应的线性表，没有的话要先创建出来；
package leetcode._102;
import javafx.util.Pair;
import java.util.*;
public class Solution102_1 {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<Pair<TreeNode, Integer>> queue
= new LinkedList<Pair<TreeNode, Integer>>();
Pair<TreeNode, Integer> pair = new Pair<TreeNode, Integer>(root, 0);
queue.add(pair);
while (!queue.isEmpty()) {
pair = queue.poll();
TreeNode front = pair.getKey();
Integer level = pair.getValue();
if (level == res.size()) {
res.add(new ArrayList<Integer>());
}
assert res.size() > level;
res.get(level).add(front.val);
if (front.left != null) {
queue.add(new Pair<TreeNode, Integer>(front.left, level + 1));
}
if (front.right != null) {
queue.add(new Pair<TreeNode, Integer>(front.right, level + 1));
}
}
return res;
}
}
