链接
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
难度： #简单
题目
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
**例如: **
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
提示：
节点总数 <= 1000
代码框架
/**
* 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) {
}
}
题目解析
解答思路1：
递归函数解法，
每次递归打印同一层的节点，
然后找出这一层节点的所有下一层的节点，
继续进行递归。
解答思路2：
递归函数解法，
在递归过程中确定元素所在层数，
然后按照层数加入到结果对应的集合中。
解答思路3：
使用辅助队列cur和next,
分别保存当前一层的节点和下一层的节点，
把cur当前一层打印出来，
然后把下一层的节点保存到next，
当cur遍历结束时，
把next赋值给cur，
再次开始打印新一层的节点，
直到cur为空时结束循环。
解答思路4：
使用一个辅助队列，
当队列不为空时，
记录下当前队列的元素个数 ，
这些元素都是属于同一层的，
打印这些同层的元素，
然后把当前元素不为空的左右节点加入队列，
完成后开始打印下一层元素，
同样记录当前队列的元素个数。
测试用例
package edu.yuwen.sowrd.num32_II.solution;
import java.util.List;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import edu.yuwen.sowrd.entity.TreeNode;
import edu.yuwen.sowrd.num32_II.sol4.Solution;
public class SolutionTest {
/**
* 给定二叉树: [3,9,20,null,null,15,7]
* 3
* / \
*9 20
* / \
* 15 7
* 返回[3,9,20,15,7]
*/
@Test
public void testCase1() {
Solution solution = new Solution();
TreeNode node1 = new TreeNode(3);
TreeNode node2 = new TreeNode(9);
TreeNode node3 = new TreeNode(20);
TreeNode node4 = new TreeNode(15);
TreeNode node5 = new TreeNode(7);
node1.left = node2;
node1.right = node3;
node3.left = node4;
node3.right = node5;
TreeNode root = node1;
List<List<Integer>> res = solution.levelOrder(root);
int[][] expected = { { 3 }, { 9, 20 }, { 15, 7 } };
for (int i = 0; i < expected.length; i++) {
int[] resArray = res.get(i).stream().mapToInt(Integer::intValue)
.toArray();
Assertions.assertArrayEquals(expected[i], resArray);
}
}
}
解答1
package edu.yuwen.sowrd.num32_II.sol1;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import edu.yuwen.sowrd.entity.TreeNode;
public class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return res;
}
List<TreeNode> nodes = Collections.singletonList(root);
recurve(nodes);
return res;
}
private void recurve(List<TreeNode> nodes) {
// 没有节点需要处理了，则结束递归
if (nodes == null || nodes.size() == 0) {
return;
}
// 打印当前同一层的节点
List<Integer> level = new ArrayList<>();
// 找出所有的下一层节点
List<TreeNode> nextNodes = new ArrayList<>();
for (TreeNode node : nodes) {
level.add(node.val);
if (node.left != null) {
nextNodes.add(node.left);
}
if (node.right != null) {
nextNodes.add(node.right);
}
}
res.add(level);
// 递归处理下一层节点
recurve(nextNodes);
}
}
解答2 推荐
package edu.yuwen.sowrd.num32_II.sol2;
import java.util.ArrayList;
import java.util.List;
import edu.yuwen.sowrd.entity.TreeNode;
public class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return res;
}
// root节点在0层
recurve(root, 0);
return res;
}
/**
* 当前节点及所在层
*/
private void recurve(TreeNode node, int k) {
// 节点为空时，结束递归
if (node == null) {
return;
}
// k大于结果集的最大索引，初始化新的一层集合
if (k > res.size() - 1) {
res.add(new ArrayList<>());
}
// 当前节点记录到当前层对应的集合
List<Integer> level = res.get(k);
level.add(node.val);
recurve(node.left, k + 1);
recurve(node.right, k + 1);
}
}
解答3
package edu.yuwen.sowrd.num32_II.sol3;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import edu.yuwen.sowrd.entity.TreeNode;
public class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return res;
}
// 当前层节点
Queue<TreeNode> cur = new LinkedList<>();
// 下一层节点
Queue<TreeNode> next = new LinkedList<>();
// 使用头结点初始化当前层
cur.offer(root);
// 当前层为空时，结束循环
while (!cur.isEmpty()) {
List<Integer> level = new ArrayList<>();
while (!cur.isEmpty()) {
TreeNode node = cur.poll();
level.add(node.val);
if (node.left != null) {
next.offer(node.left);
}
if (node.right != null) {
next.offer(node.right);
}
}
res.add(level);
// 将next和cur交换
Queue<TreeNode> temp = cur;
cur = next;
next = temp;
}
return res;
}
}
解答4
package edu.yuwen.sowrd.num32_II.sol4;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import edu.yuwen.sowrd.entity.TreeNode;
public class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return res;
}
// 队列及初始化
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
// 当前层的元素数量
int count = q.size();
// 记录当前层的元素
List<Integer> level = new ArrayList<>(count);
for (int i = 0; i < count; i++) {
TreeNode node = q.poll();
level.add(node.val);
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
/**
* 更优的写法：
* for (int i = q.siez(); i >0; i--)
*/
res.add(level);
}
return res;
}
}
网友评论