LeetCode : 111. Minimum Depth of Binary Tree

기본적인 Tree의 높이를 확인한느 문제였다.

Tree는 bfs, dfs로 모두 풀 수 있는데,,, 문제의 분류가 bfs길래 bfs로 풀이해보았다!

 

[메인 로직]

node의 right, left부분이 모두 NULL일때가 그 node가 leftNode라는 것을 의미한다.

따라서, 그 때 높이를 측정해주었다.

bfs일 경우 너비 우선탐색을 하기 때문에 먼저 발견된 leftNode가 가장 최소의 높이를 가진 노드일 수밖에 없다.

 

class Solution {
public:
    queue<pair<TreeNode*, int>> q;
    int MinLevel = INT_MAX;
    
    int minDepth(TreeNode* root) {
        if(root==NULL){
            return 0;
        }
        
        q.push(make_pair(root, 1));
        while(!q.empty()){
            TreeNode* node = q.front().first;
            int level = q.front().second;
            q.pop();
            
            if(node->left==NULL && node->right==NULL){
                MinLevel = min(MinLevel, level);
                break;
            }
            
            if(node->left!=NULL){
               q.push(make_pair(node->left, level+1)); 
            }
            
            if(node->right!=NULL){
                q.push(make_pair(node->right, level+1));
            }
        }
        
        return MinLevel;
    }
};