[LeetCode] 103. Binary Tree Zigzag Level Order Traversal
Problem
Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[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].
- -100 <= Node.val <= 100
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>> zigzagLevelOrder(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.size() != 0) {
List<Integer> tmpList = new ArrayList<Integer>();
int level = queue.size();
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);
if (list.size() % 2 == 0)
tmpList.add(queue.poll().val);
else
tmpList.add(0, 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],[20,9],[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에 들어가도록 한다.- 다음 층으로 내려가면서 임시 리스트에 값을 담을 때, 왼쪽에서 오른쪽방향이 아닌, 층마다 방향이 바뀌기 때문에 층마다 달라지는 기준을 가지고 임시 리스트에 값을 넣어야 한다.
- 층마다 달라지는 값은, 반환을 위해 선언한 리스트의 크기를 이용할 수 있으므로,
if 조건문을 작성해 층마다 다른 방향으로 임시리스트에 값이 담기도록 한다.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); // n층 노드의 값을 임시 리스트에 담는다. if (list.size() % 2 == 0) tmpList.add(queue.poll().val); else tmpList.add(0, queue.poll().val); } - 위의
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); if (list.size() % 2 == 0) tmpList.add(queue.poll().val); else tmpList.add(0, queue.poll().val); } list.add(tmpList); } root 노드가 null이면while 반복문을 진행할 수 없기 때문에, 결과 반환을 위한 리스트를 선언한 직후에if 조건문을 작성하여 빈 리스트를 반환할 수 있도록 한다.if (root == null) return list;- 만들어진 최종리스트를 반환한다.
return list;
Leave a comment