[Leetcode(릿코드)] 111. Minimum Depth of Binary Tree (Easy)

BFS 문제

leetcode.com/problems/minimum-depth-of-binary-tree/

Minimum Depth of Binary Tree - LeetCode

---

문제

루트 노드에서 시작해서 리프 노드까지 가장 짧은 거리를 구하는 문제이다

dfs 문제에서 골랐는데, bfs로 푸는 게 더 적합한 듯하다

 

해결

BFS로 탐색하다가 자식노드가 없으면 더이상 탐색하지 않는다

private static int bfs(TreeNode root) {
    if (root == null) return 0;
    Queue<List<TreeNode>> queue = new LinkedList<>();
    List<List<TreeNode>> result = new ArrayList<>();
    queue.add(List.of(root));

    boolean isSearch = false;

    while (!queue.isEmpty() && !isSearch) {
        List<TreeNode> list = new ArrayList<>();
        List<TreeNode> pop = queue.poll();
        list.addAll(pop);

        List<TreeNode> queueList = new ArrayList<>();

        for (TreeNode node : pop) {
            if (node.left == null && node.right == null) {
                isSearch = true;
                break;
            }

            if (node.left != null) queueList.add(node.left);
            if (node.right != null) queueList.add(node.right);
        }

        if (!queueList.isEmpty()) queue.add(queueList);
        if (!list.isEmpty()) result.add(list);
    }

    return result.size();
}