剑指 Offer 32 - II. 从上到下打印二叉树 II
题目
题目链接
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
解题思路
具体思路
解决方案采取了广度优先的思想
因为要求按层将数据归类到一个数组里,因此考虑按层进行遍历
那么问题来了,同一层级的节点分布在不同的二叉树的枝桠上,那如何归纳这些节点?
答:由于第一层只会有一个节点,因此只需要从第一层开始,就将每个层上的左右节点按顺序放到队列里(先进先出)。下次遍历下一层节点时,由于节点本身有序,放入左右节点时也是有序的,因此能有序的得出最终结果。
具体代码
/**
* 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>> result = new ArrayList<>();
// root 为空情况判断
if (root != null) {
// 当前层的节点
Queue<TreeNode> current = new LinkedList<>();
// 下一层的节点
Queue<TreeNode> next = new LinkedList<>();
current.add(root);
result.add(new ArrayList<>());
TreeNode node;
// 只要当前层还有节点要处理,就一直处理
while (!current.isEmpty()) {
// 节点出队
node = current.poll();
// 将 val 添加进最后一个集合的尾部
result.get(result.size() - 1).add(node.val);
// 判断是否有左右节点,有的话入队
if (node.left != null) {
next.add(node.left);
}
if (node.right != null) {
next.add(node.right);
}
// 当前节点为空了,说明当前层的数据处理完了,要处理下一层的数据了
if (current.isEmpty()) {
// 将当前层切换到下一层
current = next;
// 初始化下一层数据
next = new LinkedList<>();
// 当前层切换到下一层后,如果是有数据的,说明还要继续处理,初始化下一层的集合
if (!current.isEmpty()) {
result.add(new ArrayList<>());
}
}
}
}
return result;
}
}