C++LeetCode 구현(111.이 진 트 리 의 최소 깊이)

[LeetCode]111.Minimum Depth of Binary Tree 이 진 트 리 의 최소 깊이
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:
Given binary tree [3,9,20,null,null,15,7],
    3
/ \
9  20
/  \
15   7
return its minimum depth = 2.
이 진 트 리 의 전형 적 인 문제 의 가장 작은 깊이 문 제 는 가장 짧 은 경로 의 노드 갯 수 입 니까?아니면 DFS 를 깊이 있 게 검색 해서 완성 하 는 것 입 니까?만능 재 귀 입 니까?우선 공 을 판정 하고 현재 결점 이 존재 하지 않 으 면 바로 0 으로 돌아 갑 니 다.그리고 왼쪽 노드 가 존재 하지 않 는 다 면 오른쪽 노드 에 재 귀 함 수 를 호출 하고 1 을 추가 합 니 다.반대로 오른쪽 노드 가 존재 하지 않 으 면 왼쪽 노드 에 재 귀 함 수 를 호출 하고 1 을 추가 합 니 다.만약 에 좌우 자 결점 이 모두 존재 한다 면 좌우 자 결점 에 대해 재 귀 함 수 를 호출 하고 이들 의 작은 값 을 1 로 되 돌려 주면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

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

우 리 는 반복 해서 할 수 있 습 니 다.층 차 를 옮 겨 다 니 며 옮 겨 다 니 는 층 수 를 기록 할 수 있 습 니 다.첫 번 째 잎 결점 에 옮 겨 다 니 면 현재 층 수 를 되 돌려 줍 니 다.즉,이 진 트 리 의 최소 깊이 입 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

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

Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/111
유사 한 제목:
Binary Tree Level Order Traversal
Maximum Depth of Binary Tree
참고 자료:
https://leetcode.com/problems/minimum-depth-of-binary-tree/
https://leetcode.com/problems/minimum-depth-of-binary-tree/discuss/36153/My-concise-c%2B%2B-solution
https://leetcode.com/problems/minimum-depth-of-binary-tree/discuss/36071/BFS-C%2B%2B-8ms-Beats-99.94-submissions
C++구현 LeetCode(111.이 진 트 리 의 최소 깊이)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 이 진 트 리 의 최소 깊이 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!