剑指 Offer 32 - I. 从上到下打印二叉树
题目
题目链接
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
解题思路
具体思路
利用队列先进先出的特点
将左右节点依次入队。后面只需要将节点依次出队，再将后续的左右节点追加到队尾即可。
示例：
22
/ \
12 16
/ \ / \
7 8 11 15
将 22 入队。队列：[22]，结果：[]
将 22 出队，并将 12，16 入队。队列：[12, 16]，结果：[22]
将 12 出队，将 7，8 入队。队列：[16, 7, 8]，结果：[22, 12]
将 16 出队，将 11, 15 入队。队列：[7, 8, 11, 15]，结果：[22, 12, 16]
将 7, 8, 11, 15 依次出队。队列：[]，结果：[22, 12, 16, 7, 8, 11, 15]
具体代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> values = new ArrayList<>();
public int[] levelOrder(TreeNode root) {
if (root == null) {
return new int[0];
}
// 创建队列用于缓存节点
Queue<TreeNode> nodes = new LinkedList<>();
nodes.add(root);
// 开始循环获取 val，并且依次将子节点入队
while (!nodes.isEmpty()) {
printNode(nodes);
}
// 把集合转数组
int[] result = new int[values.size()];
for (int i = 0; i < values.size(); i++) {
result[i] = values.get(i);
}
return result;
}
private void printNode(Queue<TreeNode> nodes) {
TreeNode node = nodes.poll();
values.add(node.val);
if (node.left != null) {
nodes.add(node.left);
}
if (node.right != null) {
nodes.add(node.right);
}
}
}