题目
给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。
例如: 给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
题解
我们数据结构的书上教的层序遍历, 就是利用一个队列, 不断的把左子树和右子树入队。但是这个题目还要要求按照层输出。所以关键的问题是：如何确定是在同一层的。我们很自然的想到：如果在入队之前, 把上一层所有的节点出队, 那么出队的这些节点就是上一层的列表。由于队列是先进先出的数据结构, 所以这个列表是从左到右的。
/**
* 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) {
List<List<Integer>> res = new LinkedList<>();
if (root == null) {
return res;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> currentRes = new LinkedList<>();
// 当前队列的大小就是上一层的节点个数, 依次出队
while (size > 0) {
TreeNode current = queue.poll();
if (current == null) {
continue;
}
currentRes.add(current.val);
// 左子树和右子树入队.
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
size–;
}
res.add(currentRes);
}
return res;
}
}
这道题可不可以用非递归来解呢?
递归的子问题：遍历当前节点, 对于当前层, 遍历左子树的下一层层, 遍历右子树的下一层
递归结束条件: 当前层, 当前子树节点是 null
/**
* 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) {
List<List<Integer>> res = new LinkedList<>();
if (root == null) {
return res;
}
levelOrderHelper(res, root, 0);
return res;
}
/**
* @param depth 二叉树的深度
*/
private void levelOrderHelper(List<List<Integer>> res, TreeNode root, int depth) {
if (root == null) {
return;
}
if (res.size() <= depth) {
// 当前层的第一个节点, 需要 new 一个 list 来存当前层.
res.add(new LinkedList<>());
}
// depth 层, 把当前节点加入
res.get(depth).add(root.val);
// 递归的遍历下一层.
levelOrderHelper(res, root.left, depth + 1);
levelOrderHelper(res, root.right, depth + 1);
}
}
热门阅读
技术文章汇总
【Leetcode】101. 对称二叉树
【Leetcode】100. 相同的树
【Leetcode】98. 验证二叉搜索树