문제 푼 날짜 : 2021-11-30

문제

문제 링크 : https://leetcode.com/problems/minimum-depth-of-binary-tree/

접근 및 풀이

dfs를 이용하여 leaf node가 나올 때까지 탐색해주면서 depth를 구해주면 쉽게 풀 수 있는 문제였다.
bfs로도 풀 수가 있는데, discussion을 참조하여 bfs로도 구현해보았다.
이 문제에서는 dfs보다 bfs가 최악의 경우에 더 좋은 성능을 낼 수가 있다. 여기서 최악의 경우란, Tree가 한 쪽으로 치우친 unbalanced tree일 경우이다.
문제에서는 그렇게 큰 입력이 주어지지 않아서 성능차이가 크게 나타나진 않았지만, Tree를 순회하는데 있어 두 방법 모두 유용하기 때문에 알아둬야할 것 같다.

코드(dfs)

class Solution {
public:
    int dfs(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        if (node->left == nullptr) {
            return 1 + dfs(node->right);
        }
        if (node->right == nullptr) {
            return 1 + dfs(node->left);
        }
        return 1 + min(dfs(node->left), dfs(node->right));
    }
    int minDepth(TreeNode* root) {
        return dfs(root);
    }
};

코드(bfs)

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

결과

피드백

이미지 출처 : https://aerocode.net/190