[LeetCode/JAVA] 103. Binary Tree Zigzag Level Order Traversal

https://github.com/ROUTINE-STUDY/Algorithm

ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다.
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 : https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Binary Tree Zigzag Level Order Traversal - LeetCode

문제 설명

출처 : LeetCode

이진트리가 주어지고, 해당 트리를 지그재그로 탐색하여 반환하세요.

풀이 방법

쉬워 보였지만 만만치 않았던 문제입니다.
Queue를 2개를 사용하여 풀이했습니다.
1번 Queue = 정상적인 BFS 탐색을 위한 Queue (좌측부터 탐색)
2번 Queue = 반대 BFS 탐색을 위한 Queue (우측부터 탐색)
위의 로직대로 탐색 시 Queue에  각각 적재합니다.
count 값으로 홀수/짝수를 구분하여 depth가 홀수 일 때 역 탐색을 합니다.

설명을 위한 그림

위 그림 처럼 Queue1은 정상 BFS 흐름(좌측부터 탐색), Queue2는 우측부터 탐색하도록 적재하였습니다.

노란색 바탕면 흐름을 따라 결과를 삽입해 줍니다.

지그재그로 탐색해야하기 때문에, depth가 홀수일 때는 Queue2에 있는 Node의 값을 넣어주는 방식입니다.

 

내 코드(JAVA)

 

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if(root == null) return new ArrayList<>();

    List<Integer> list = null;
    List<List<Integer>> res = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<>();
    Queue<TreeNode> q2 = new LinkedList<>();

    int count = 0;
    q.offer(root);
    q2.offer(root);

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

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

            // depth가 짝수일땐 정상, 홀수일땐 역으로 탐색하여 지그재그 구현
            if(count%2 == 0) {
                list.add(node.val);
            } else {
                list.add(node2.val);
            }

            // 첫 번째 큐에는 정상 BFS 탐색 흐름
            if(node.left != null) q.offer(node.left);
            if(node.right != null) q.offer(node.right);

            // 두 번째 큐에는 역 BFS 탐색 흐름
            if(node2.right != null) q2.offer(node2.right);
            if(node2.left != null) q2.offer(node2.left);
        }
        count++;
        res.add(list);
    }

    return res;
}