102. Binary Tree Level Order Traversal

https://leetcode.com/problems/binary-tree-level-order-traversal/description/?envType=study-plan-v2&envId=top-interview-150

Binary Tree Level Order Traversal - LeetCode

1.아이디어

트리를 레벨별 순회하여 2차원 리스트에 담아 리턴하는 문제입니다.

 

 

2.도식화

레벨 0부터 전위 순회하여 [ [ 3] , [ 9, 20] , [ 15, 7 ] 을 2차원 리스트에 담아 리턴합니다.

먼저 queue에 root노드를 offer합니다. 

 

 

그리고 queue의 사이즈 만큼 자식노드를 queue에 offer하는 반복문을 실행합니다.

200번지 노드와 300번지 노드를 queue에 offer합니다.

그리고 queue에 있는 값을 빼내고 리스트에 add합니다.

 

queue에는 레벨 0의 100번지 노드에 해당하는 로직이 끝나고

queue에는 200번지와 300번지에 해당하는 9와 20이 담겨져 있습니다.

반복하면 리스트에 전위순회를 실행한 순서대로 값이 들어갑니다.

 

 

 

 

 

 

 

 

 

 

 

 

3.소스코드

/**
 * 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;
 *     }
 * }
 */
 import java.util.*;
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        if(root == null)return list;

        queue.offer(root);

        while(!queue.isEmpty())
        {
            int level = queue.size();
            List<Integer> subLevels = new ArrayList<>();


            for(int i = 0; i < level; i++)
            {
                if(queue.peek().left!=null)
                {
                    queue.offer(queue.peek().left);
                }
                if(queue.peek().right!=null)
                {
                    queue.offer(queue.peek().right);
                }
                subLevels.add(queue.remove().val);
            }
            list.add(subLevels);


            
        }

        return list;
    }
}