[Queue문제] - ZigZagOrder

 

위와 같은 트리가 있을 때, [[1], [3, 2], [4, 5]] 의 결과를 출력하라

 

 

트리를 탐색하는데, 한번씩 방문 순서를 지그 재그 형태로 바꿔가면서 탐색을 해야 하는 문제이다.

일반적으로 트리를 preorder(전위순회)로 순회하지만, L, R 부분을 바꿔가면서 탐색하도록 해야 한다.
간단하게 boolean 타입 플래그를 두고, L와 R 노드를 방문하는 순서를 바꿔주면 된다.

 

package inflearn.queue;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode {
	public int val;
	public TreeNode left;
	public TreeNode right;

	public TreeNode(int val) {
		this.val = val;
	}
}

public class ZigZagTreeOrder {

	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);
		root.left.left = new TreeNode(4);
		root.left.right = new TreeNode(5);

		ZigZagTreeOrder zigZagTreeOrder = new ZigZagTreeOrder();
		System.out.println(zigZagTreeOrder.solve(root));
	}

	public List<List<Integer>> solve(TreeNode root) {
		Queue<TreeNode> queue = new LinkedList<>();
		List<List<Integer>> result = new ArrayList<>();
		boolean normalProcessing = true;
		queue.offer(root);

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

			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				if (normalProcessing) {
					list.add(node.val);
				} else {
					list.add(0, node.val);
				}

				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
			normalProcessing = !normalProcessing;
			result.add(list);
		}

		return result;
	}
}