https://leetcode.com/problems/binary-tree-level-order-traversal/description/
Binary Tree Level Order Traversal - LeetCode
Can you solve this real interview question? Binary Tree Level Order Traversal - Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level). Example 1: [https://assets.leetcode.com/u
leetcode.com
주어진 커스텀 클래스인 이진트리 노드를 레벨에 따른 중첩 List배열로 반환하는 문제이다.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> answer = new ArrayList<>();
if (root == null) {
return answer;
}
Queue<TreeNode> que = new ArrayDeque<>();
que.offer(root);
while (!que.isEmpty()) {
List<Integer> levelList = new ArrayList<>();
int queSize = que.size();
while (queSize-- > 0) {
TreeNode node = que.poll();
levelList.add(node.val);
if (node.left != null) {
que.offer(node.left);
}
if (node.right != null) {
que.offer(node.right);
}
}
if (levelList.size() > 0) {
answer.add(levelList);
}
}
return answer;
}
}
레벨 단위로 처리하기 위해서 Queue를 이용하였다. 하나의 레벨을 Queue 에 넣어 전부 꺼내며 리스트를 완성하고, 전부 꺼내는 동안 다음 레벨의 노드를 Queue에 넣어 순차적으로 레벨 List를 만들어 주었다. 하나의 레벨을 꺼내며 Queue에 새로 넣기 때문에 하나의 레벨을 빼내기 전에 사이즈를 체크해서 꺼내면 된다.