[Grind75-LeetCode] Binary Tree Level Order Traversal JAVA

반응형

728x90

[Grind75-LeetCode] Binary Tree Level Order Traversal - Medium 

---

접근

• 재귀

---

풀이

이진트리를 레벨별로 List에 담아 출력하는 문제이다. 이진트리는 TreeNode 형태로 현재 노드의 값, 왼쪽 서브트리, 오른쪽 서브트리를 가지는 객체 형태로 주어진다.

출처: LeetCode

예제 1번으로 주어지는 트리의 모습인데 각 레벨별 노드 값을 List<List<Integer>> 형태로 반환해야 하는데 현재 트리에선 루트 노드인 레벨 0 [3], 레벨 1 [9, 20], 레벨 2 [15,7]로 [ [3], [9,20], [15,7] ] 형태의 결과를 반환해야 한다. 이 문제 또한 재귀를 이용해 간단하게 풀 수 있는 문제로 리스트의 인덱스와 트리의 레벨을 매칭시켜 각각 해당하는 위치에 넣어주면 된다.

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        makeOrder(root, 0, result);
        
        return result;
    }

메서드는 반환값 없이 리스트를 참조해 값을 넣어줄 것이므로 void로 선언했다.

    public void makeOrder(TreeNode treeNode, int level, List<List<Integer>> result) {
        if (treeNode == null) {
            return;
        }
        
        if (result.size() <= level) {
            result.add(new ArrayList<>());
        }
        result.get(level).add(treeNode.val);

        makeOrder(treeNode.left, level + 1, result);
        makeOrder(treeNode.right, level + 1, result);
    }

서브 트리가 null일 경우 종료된다. 서브 트리가 존재할 경우 level에 맞춰 리스트에 값을 추가하게 되는데 현재 리스트의 크기가 level 보다 작거나 같을 경우 아직 해당 레벨의 리스트가 만들어지지 않아 리스트를 추가해 준다. 값을 넣은 뒤 현재 노드의 왼쪽 오른쪽 서브트리를 재귀를 통해 진행하여 준다.  

---

전체 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        makeOrder(root, 0, result);
        
        return result;
    }

    public void makeOrder(TreeNode treeNode, int level, List<List<Integer>> result) {
        if (treeNode == null) {
            return;
        }
        
        if (result.size() <= level) {
            result.add(new ArrayList<>());
        }
        result.get(level).add(treeNode.val);

        makeOrder(treeNode.left, level + 1, result);
        makeOrder(treeNode.right, level + 1, result);
    }
}

실행 시간 0ms에 100% Beats로 의도한 방법을 통해 해결하였기 때문에 추가로 다른 코드를 분석하진 않았다.