[LeetCode] 102. Binary Tree Level Order Traversal

Problem

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:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000

---

Solution

/**
 * 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>> list = new ArrayList<List<Integer>>();
        if (root == null)
            return list;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (queue.isEmpty() == false) {
            int level = queue.size();
            List<Integer> tmpList = new ArrayList<Integer>();
            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);
                tmpList.add(queue.poll().val);
            }
            list.add(tmpList);
        }
        return list;
    }
}

Explanation

• 결과 반환을 위한 리스트를 선언한다.

  List<List<Integer>> list = new ArrayList<List<Integer>>();
  

• 문제의 반환 값은 아래와 같이 큰 리스트 안에 작은 리스트들로 구성되어 있다.
• 이것이 의미하는 것은, 먼저 작은 리스트를 만들어서 큰 리스트에 추가하는 작업이 필요하다는 것이다.

  Input: root = [3,9,20,null,null,15,7]
  Output: [[3],[9,20],[15,7]]
  

• 작은 리스트를 만들기 위해 임시 리스트를 선언한다.

  List<Integer> tmpList = new ArrayList<Integer>();
  

• 임시 리스트에 root 노드값을 추가한다.

  tmpList.add(root.val);
  

• 임시 리스트를 통해 만들어진 작은 리스트를 큰 리스트에 추가한다.

  list.add(tmpList);
  

• 이제 이 과정을 트리의 아래쪽으로 내려오면서 층 마다 진행을 해야하는데, 층마다 자리하고 있는 노드를 자료구조에 넣어서 활용하면 문제를 좀 더 쉽게 직관적으로 해결할 수 있다.
• 아래와 같은 순서로 각 층의 노드가 순차적으로 작은 리스트로 삽입되고, 만들어진 작은 리스트가 큰 리스트에 추가되면서 최종적으로 큰 리스트가 만들어진다는 것을 감안하면 자료구조 Queue를 생각할 수 있다.

• 자료구조 Queue를 선언하고, 먼저 root 노드를 Queue에 넣는다.

  Queue<TreeNode> queue = new LinkedList<TreeNode>();
  queue.offer(root); // n층을 Queue에 담는다.
  

• Queue에 담긴 root 노드를 임시 리스트인 tmpList에 넣은 후, 결과 반환을 위한 리스트인 List에 담는다.

  tmpList.add(queue.poll().val); // n층을 임시 리스트에 담는다.
  list.add(tmpList); // n층을 최종 리스트에 담는다.
  

• 다음 층으로 내려가면서 리스트를 완성하기 위해서는 부모 노드로 임시 리스트를 만드는 동안, 그 자식 노드들이 Queue에 들어가서 임시 리스트로 만들어지길 기다리게 만들면 된다.
• for 반복문을 작성하여 부모 노드가 임시 리스트에 담기는 동안 자식 노드가 Queue에 들어가도록 한다.

  for (int i = 0; i < queue.size(); i++) {
    // n + 1층을 큐에 담는다.
    if (queue.peek().left != null)
        queue.offer(queue.peek().left);
    if (queue.peek().right != null)
        queue.offer(queue.peek().right);
    tmpList.add(queue.poll().val); // n층을 임시 리스트에 담는다.
  }
  

• 위의 for 반복문은 트리의 한 층만을 임시 리스트로 만들고, 만들어진 임시 리스트를 최종 리스트에 넣기 때문에, while 반복문으로 감싸서 모든 층에 진행될 수 있도록 한다.
• 그리고 Queue의 크기만큼 for 반복문이 실행되어야하고, 그렇다면 for 반복문의 조건식으로 Queue의 크기를 넘겨주어야 하는데 for 반복문을 진행하면서 Queue의 사이즈가 변경되기 때문에, 반복되어야 하는 Queue의 크기를 for 반복문의 바깥에 선언하여 for 반복문이 진행되는 동안 for 반복문의 조건식이 변경되지 않도록 한다.

  while (queue.isEmpty() == false) {
    int level = queue.size();
    List<Integer> tmpList = new ArrayList<Integer>();
    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);
        tmpList.add(queue.poll().val);
    }
    list.add(tmpList);
  }
  

• root 노드가 null이면 while 반복문을 진행할 수 없기 때문에, 결과 반환을 위한 리스트를 선언한 직후에 if 조건문을 작성하여 빈 리스트를 반환할 수 있도록 한다.

  if (root == null)
    return list;
  

• 만들어진 최종리스트를 반환한다.

  return list;