LeetCode(111) Minimum Depth of Binary Tree

2226 단어

제목


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.

분석


두 갈래 나무의 최소 깊이를 구합니다. 뿌리 노드에서 가장 가까운 잎 노드까지의 경로 길이입니다.
마찬가지로 귀속적인 사상을 채택한다.
  • 루트 노드가 비어 있으면 0을 되돌려줍니다
  • 뿌리 노드가 유일한 두 갈래 나무 노드일 때 1;
  • 그렇지 않으면 해답을 구하고 최소(비공, 최종적으로 잎 노드에 도달할 수 있음) 좌우 자수 깊이 + 1을 되돌려줍니다

  • AC 코드

    class Solution {
    public:
        int minDepth(TreeNode* root) {
            if (!root)
                return 0;
            // 
            else if (!root->left && !root->right)
                return 1;
            else{
                int left_depth, right_depth;
                if (root->left)
                    left_depth = minDepth(root->left);
                else
                    left_depth = INT_MAX;
                if (root->right)
                    right_depth = minDepth(root->right);
                else
                    right_depth = INT_MAX;
                return min(left_depth, right_depth) + 1;
            }
    
        }
    };
    

    GitHub 테스트 프로그램 소스

    좋은 웹페이지 즐겨찾기