[LeetCode] 111. Minimum Depth of Binary Tree

https://leetcode.com/problems/minimum-depth-of-binary-tree/description/

Minimum Depth of Binary Tree - LeetCode

문제 유형 : BFS / DFS

문제 난이도 : Easy

 

문제

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

 

이진 트리가 주어진다. 이 트리의 최소 깊이를 구하여라.

최소 깊이란 루트에서 가장 가까운 잎 노드까지의 깊이를 말한다.

 

풀이

BFS의 경우 : 트리를 순회하다가, 최초로 잎 노드를 만나면 멈추면 된다.

 

DFS의 경우 : 각 경우의 깊이들을 비교하여 가장 작은 깊이를 출력한다.

 

코드(C++, BFS 코드)

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL)
            return 0;
        
        queue<TreeNode*> q;
        q.push(root);
        int depth = 0;
        
        while (!q.empty()) {
            int size = q.size();
            depth++;
            
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                
                if (node->left == NULL && node->right == NULL)
                    return depth;
                
                if (node->left)
                    q.push(node->left);
                
                if (node->right)
                    q.push(node->right);
            }
        }
        
        return 0;
    }
};