문제

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

binary tree가 지정되면 노드 값의 지그재그 수준 트래버설(transversal)을 반환하십시오. (즉, 왼쪽에서 오른쪽으로, 그리고 오른쪽에서 왼쪽으로 다음 레벨에서 다시 왼쪽에서 오른쪽으로 번갈아서).

For example :

Given binary tree [3,9,20,11,5,15,7]

      3
    /   \
   9     20
  / \   /  \
 11  5 15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [11,5,15,7]
]

기본 지식

스택(Stack)

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조

pop(): 스택에서 가장 위에 있는 항목을 제거한다.
push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
peek(): 스택의 가장 위에 있는 항목을 반환한다.
isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

풀이

이번 문제의 핵심은 식별자 flag를 두어 true이면 왼쪽 자식노드 부터, false이면 오른쪽 자식노드 부터 탐색 하도록 하는 것입니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root==null) return ret;
        
        boolean flag = true;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while(!stack.isEmpty()){
            int size = stack.size();
            Stack<TreeNode> newStack = new Stack<>();
            List<Integer> level = new ArrayList<>();
            for(int i=0; i<size; i++){
                //현재 레벨 노드의 자손들 처리
                TreeNode node = stack.pop();
                level.add(node.val);
                if(flag){
                    if(node.left!=null) newStack.push(node.left);
                    if(node.right!=null) newStack.push(node.right);
                }else{
                    if(node.right!=null) newStack.push(node.right);
                    if(node.left!=null) newStack.push(node.left);
                }
            }
            ret.add(level);
            stack = newStack;
            flag = !flag;
        }
        
        return ret;
    }
}

처음에 flag를 true, root 노드를 stack에 넣습니다

flag = true
stack : 3

첫번째 while 문을 통과하면 다음과 같습니다.

flag = true
stack : 3
size = 1
level : 3
newStack : 9 20

for문 통과 후
flag = false
stack : 9 20
ret : [3]

두번째 while 문을 통과하면 다음과 같습니다.

flag = false
stack : 9 20
size = 2

for ( i = 0 )
node = 20
stack : 9
level : 20
newStack : 7 15

for ( i = 1 )
node = 9
stack :
level = 20 9
newStack : 7 15 5 11

for문 통과 후
flag = true
stack : 7 15 5 11
ret : [3] [20.9]

세번째 while 문을 통과하면 다음과 같습니다.

flag = true
stack : 7 15 5 11
size = 4

for ( i = 0)
node = 11
stack : 7 15 5
level : 11
newStack :    (null이므로 stack에 쌓이지 않음)

for ( i = 1 )
node = 5
stack : 7 15
level : 11 5
newStack :    (null이므로 stack에 쌓이지 않음)

for ( i = 2 )
node = 15
stack : 7
level : 11 5 15
newStack :    (null이므로 stack에 쌓이지 않음)

for ( i = 3 )
node = 7
stack :
level : 11 5 15 7
newStack :    (null이므로 stack에 쌓이지 않음)

for문 통과 후
flag = false
stack : 
ret : [3], [20.9], [11,5,15,7]

위와 같이 식별자 flag를 두어 트리의 높이(level)에 따라 오른쪽 또는 왼쪽으로 탐색하며 stack에 쌓아두며 그에 따라 리스트(ret)에 추가하여 level별로 관리합니다.

출처 : 제가 알고리즘 문제에 막 감을 익히고 있는 단계여서 유튜버 승지니어님의 코드를 인용하였습니다. 도움되는 영상이 많이 있으므로 많은 방문 부탁드리겠습니다.

유튜브 승지니어 해당영상

← Previous Post

LeetCode#103

Binary Tree Zigzag Level Order Traversal

문제

기본 지식

풀이