[LeetCode] 102. Binary Tree Level Order Traversal - 문제풀이

Description

주어진 트리를 층별로 순회하며 순서대로 층별 요소의 목록을 반환하는 문제입니다. Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000

Solution 1. DFS - Recursion(재귀)

public List<List<Integer>> levelOrder(TreeNode root) {
    //1. Recursion(DFS)
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    levelorderTraversal(result,0,root);
    return result;

}
private void levelorderTraversal(List<List<Integer>> result, int level, TreeNode node) {
    if(node == null){return;}
    if(result.size() <= level){  // 현재 level List가 없을 경우  ex)size가 1이면 0뎁스까지밖에 없음. 1뎁스일때 만들어줘야함.
        List<Integer> row = new ArrayList<>();
        row.add(node.val);
        result.add(row);
    }else{
        List<Integer> row = result.get(level);
        row.add(node.val);
    }
    levelorderTraversal(result, level+1,node.left);
    levelorderTraversal(result, level+1,node.right);
}

깊이우선탐색(DFS)과 유사하게 재귀호출을 통해 탐색하는 방법입니다. level별로 List를 만들어주기 위해 각 노드를 재귀호출할때 level을 넘겨주고 해당 level의 list가 없으면 새로 생성해준 뒤 요소를 추가해줍니다.

Solution 2. BFS - Queue

public List<List<Integer>> levelOrder2(TreeNode root) {
    //2. Iteration (BFS with Queue)
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if(root == null)return result;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while(!q.isEmpty()){
        int qSize = q.size();
        List<Integer> row = new ArrayList<>();
        for (int i = 0; i < qSize; i++) {

            TreeNode cur = q.poll();
            row.add(cur.val);
            if(cur.left != null) q.offer(cur.left);
            if(cur.right != null) q.offer(cur.right);

        }
        result.add(row);
    }
    
    return result;
}

너비우선 탐색(BFS)으로 큐를 이용한 방법입니다. 먼저 루트값을 list에 쓴뒤 left,right순으로 queue에 담아 순차적으로 값을 읽어냅니다. level별 List는 각 queue의 사이즈를 체크하여 만들어줍니다.

Reference

Binary Tree Level Order Traversal - LeetCode

LeetCode, Algorithm, String, Hash Table, LinkedList, Depth-First Search, Breadth-First Search, Matrix, TwoPoint, Array, Recusion, 릿코드, 알고리즘, 코딩테스트, 코테, 문제풀이

Binary Tree, Recusion, 전위순회, inorder-traversal

중위순회, inorder-traversal, 후위순회, postorder-traversal,