给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。
例如: 给定二叉树: [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);
}
}
1
8a9a09dw12 2019-02-26 09:44:00 +08:00
现在去 leetcode 上写个二叉树遍历也可以拿出来的吹了吗?
|
2
JasonSi 2019-02-26 09:49:46 +08:00 1
@8a9a09dw12 说明你不是目标用户( doge
|
3
8a9a09dw12 2019-02-26 09:55:04 +08:00
@JasonSi 垃圾营销号真的恶心
|
4
Bryan0Z 2019-02-26 10:25:32 +08:00 via Android
道理我都懂,不就是 BFS 嘛…
|
5
holy_sin 2019-02-26 10:36:58 +08:00
老铁 这是要连发 900 帖吗
|
6
11232as 2019-02-26 10:39:38 +08:00
这不是数据结构基础???
|
7
mskf 2019-02-26 10:41:42 +08:00
上面用队列的非递归,下面是递归,那你中间一句话有问题啊,啥叫 这道题可不可以用非递归来解呢?
|