(Leet Code c++)Minimum Depth of Binary Tree

111. Minimum Depth of Binary Tree

Easy

2713843Add to ListShare

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.

 

Example 1:

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

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6] Output: 5

 

Constraints:

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

 

주어진 이진트리에서 최소 depth를 찾아야 한다.

최소 depth는 루트에서 리프 노드까지의 depth 중 가장 짧은 depth를 뜻한다.

 

dfs를 통해 가능하지만,

가장 짧은 높이를 찾기 위해 bfs를 활용했다.

 

주어진 root가 NULL이 아니라면 큐에 넣어 높이를 구한다.

가장 짧은 depth는 리프 노드를 뜻하므로 왼쪽 자식 노드와 오른쪽 자식 노드가 NULL인 경우 바로 depth를 리턴하면 된다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        queue<pair<TreeNode *, int>> q;
        int depth = 0;
        
        if(root != NULL){
            q.push(make_pair(root, 1));
            
            while(!q.empty()){
                int size = q.size();
                
                while(size--){
                    TreeNode * current = q.front().first;
                    int d = q.front().second;
                    
                    q.pop();
                    
                    if(current->left == NULL && current->right == NULL){
                        return d;
                    }
                    else{
                        if(current->left != NULL){
                            q.push(make_pair(current->left, d + 1));
                        }
                        
                        if(current->right != NULL){
                            q.push(make_pair(current->right, d + 1));
                        }
                    }
                }
            }
        }
        
        return depth;
    }
};