[leetcode 75] 102. Binary Tree Level Order Traversal

 

이진트리의 root가 주어지는 경우 level order 순회하기

level order란 각 트리의 level순으로 왼쪽부터 오른쪽 노드를 순차로 나열한 것

 

정답 예1) 재귀

List<List<Integer>> output = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }
    recursive(root, 0);
    return output;
}

public void recursive(TreeNode node, int level) {
    if (node == null) {
        return;
    }

    List<Integer> row;
    if (output.size() == level) { // level의 row를 처음 추가하는 경우
        row = new ArrayList<>();
        row.add(node.val);
        output.add(row);
    } else {
        row = output.get(level); // 기존 level의 row가 존재하는 경우
        row.add(node.val);
    }

    recursive(node.left, level+1);
    recursive(node.right, level+1);
}

 

정답 예2) 큐 이용

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

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        // level 당 들어있는 큐의 size
        int size = queue.size();
        List<Integer> row = new ArrayList<>();

        // for문이 돌기 전 저장된 level의 node 개수만큼 돌면서
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();

            // row에 해당 level의 node 별 값 추가
            row.add(node.val);

            // 다음 while문의 반복에서 다음 level의 node를 모두 담고 queue size 갱신
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }

        // for문 한번이 끝나면 하나의 level의 모든 node의 값이 row에 담아짐
        output.add(row);
    }

    return output;
}