103. Binary Tree Zigzag Level Order Traversal

문제

이진 트리가 주어졌을때 트리를 오른쪽 -> 왼쪽으로, 다시 왼쪽에서 -> 오른쪽으로 번갈아 가면서 순회하도록 구현하는 문제입니다.

 

예를 들어 아래와 같은 이진 트리가 주어졌을때,

3 -> 20, 9 -> 15, 7 처럼 순회한 결과를 리스트에 담아 리턴해야 합니다. 

 

문제 풀이

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();

    if(root == null) return result;

    Queue<TreeNode> q = new LinkedList<>();

    q.offer(root);
    int zigzag = 0; // 0:R, 1:L  

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

        for(int i=0; i<size; i++) {
            TreeNode node = q.poll();

            if(node.left != null) q.offer(node.left);
            if(node.right != null) q.offer(node.right);

            if(zigzag == 0) temp.addLast(node.val);
            else            temp.addFirst(node.val);
        }

        zigzag = (zigzag == 0) ? 1 : 0;

        result.add(temp);
    }

    return result;
}

 

위 풀이 코드는 큐를 이용한 BFS 풀이입니다.

 

1.  맨 처음 시작할 루트 노드를 큐에 담습니다.

2. 큐에 있는 노드를 꺼내 연관된 자식 노드들을 큐에 담고, 리스트에도 노드의 값을 추가합니다.

3. 노드 값을 추가할 때, zigzag 값에 따라 뒤에서부터 혹은 앞에서 부터 저장합니다.

4. 하나의 level (계층) 이 끝나면 zigzag 의 값을 0 <-> 1 변환해줍니다.

5. 하나의 level (계층) 이 끝나면 result 리스트에 원소들을 담고 있는 리스트를 저장하고 리턴합니다.