LetCode--두 갈래 나무의 최소 깊이를 구하다

1257 단어 LeetCode
차례로 실현되다
int minDepth(TreeNode* root) {
    //  
    if (!root){
        return 0;
    }
    else if (!root->left && !root->right){
        return 1;
    }
    else if (!root->left){
        return minDepth(root->right) + 1;
    }
    else if (!root->right){
        return minDepth(root->left) + 1;
    }
    else{
        return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
}

번갈아 실현하다
int minDepth(TreeNode* root) {
    //  
    if (!root){
        return 0;
    }
    else if (!root->left && !root->right){
        return 1;
    }
    // BFS   
    //  , 
    queue nodes;
    nodes.push(root);
    int depth = 0;
    while (!nodes.empty()){
        depth++;
        int n = nodes.size();
        while (n--){
            TreeNode* curNode = nodes.front();
            //  
            if (!curNode->left && !curNode->right){
                return depth;
            }
            if (curNode->left){
                nodes.push(curNode->left);
            }
            if (curNode->right){
                nodes.push(curNode->right);
            }
            nodes.pop();
        }
    }
}

좋은 웹페이지 즐겨찾기