103. Binary Tree Zigzag Level Order Traversal

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문제 출처

Binary Tree Zigzag Level Order Traversal - LeetCode

[문제 설명]

일반적으로 BFS는 한방향으로 쭉 읽는데 방향을 왔다갔다하면서 읽으라는 문제다.

보통 위에 구조 같으면 3/9,20/15,7 순이지만 이를 3/20,9/15,7순으로 읽으라는 문제입니다.

[처음 생각한 접근 방법]

처음 생각한 방법은 매번 넣는 방향을 바꿔주는 거였다.

그런데 이 방법으로는 성립이 전혀 안됐다.

위의 예시로 보자면 20,9를 넣었다가 15,7순으로 넣는 것인데, 만약에 9에가 자식 노드가 있었다면, 20의 자식 노드가 9의 자식 노드보다 먼저 읽히는 일이 생긴다.

그래서 생각한 방법은 그냥 BFS는 그대로 유지한채 deque를 쓰는 방식을 사용하기로 했다.

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> answer = new LinkedList<>();//배열 끝에 추가라 LinkedList가 빠를 듯?
        Deque<TreeNode> queue = new LinkedList<>();

        if (root != null) {
            boolean isPollFirst = false;
            queue.offer(root);
            answer.add(new ArrayList<>());
            answer.get(0).add(root.val);

            while (!queue.isEmpty()) {
                int size = queue.size();
                Deque<Integer> deque = new LinkedList<>();

                while (size-- > 0) {
                    TreeNode temp = queue.poll();

                    if (temp.left != null) {
                        queue.offer(temp.left);
                        deque.offer(temp.left.val);
                    }
                    if (temp.right != null) {
                        queue.offer(temp.right);
                        deque.offer(temp.right.val);
                    }
                }

                if (deque.size() != 0) {
                    List<Integer> list = new ArrayList<>();

                    if (isPollFirst) {
                        while (!deque.isEmpty()) {
                            list.add(deque.pollFirst());
                        }
                    } else {
                        while (!deque.isEmpty()) {
                            list.add(deque.pollLast());    
                        }
                    }

                    answer.add(list);
                }
                isPollFirst = !isPollFirst;
            }
        }

        return answer;
    }
}

리트코드 답안

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) 
    {
        List<List<Integer>> sol = new ArrayList<>();
        travel(root, sol, 0);
        return sol;
    }

    private void travel(TreeNode curr, List<List<Integer>> sol, int level)
    {
        if(curr == null) return;

        if(sol.size() <= level)
        {
            List<Integer> newLevel = new LinkedList<>();
            sol.add(newLevel);
        }

        List<Integer> collection  = sol.get(level);
        if(level % 2 == 0) collection.add(curr.val);
        else collection.add(0, curr.val);

        travel(curr.left, sol, level + 1);
        travel(curr.right, sol, level + 1);
    }
}

봐도 모르겠다... 다음에 봐야될듯