【LeetCode 32】111.二叉樹的最小深度

文章目錄

• ​​【LeetCode 32】111.二叉樹的最小深度​​
• ​​一、題意​​
• ​​二、思路​​

• ​​2.1遞歸法​​

一、題意

二、思路

這道題和之前求得 《104.二叉樹的最大深度》

不同，不同在邏輯處理上。注意這裡的概念， **最小深度：**最是從根節點到最近葉子節點的最短路徑上的節點數量。

2.1遞歸法

同樣是三部曲：

class Solution {
public:
//1.确定函數參數和傳回值
    int getDepth(TreeNode *node)
    {
        if(node==NULL) return 0;//2.判斷終止條件

        //3.确定單層遞歸邏輯：

        int leftDepth=getDepth(node->left);//左
        int rightDepth=getDepth(node->right);//右

        
        /*
        核心思路：
        是以，如果左子樹為空，右子樹不為空，說明最小深度是 1 + 右子樹的深度。反之，右子樹為空，左子樹不為空，最小深度是 1 + 左子樹的深度。 最後如果左右子樹都不為空，傳回左右子樹深度最小值 + 1 。    
        */
        //當左子樹為空，右子樹不為空，并不是最大深度
        if(node->left==NULL&&node->right!=NULL)
        {
            return 1+rightDepth;
        }

        if(node->left!=NULL&&node->right==NULL)
        {
            return 1+leftDepth;
        }
        int result=1+min(leftDepth,rightDepth);
        return result;
    }
    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};      

核心思路：

是以，如果左子樹為空，右子樹不為空，說明最小深度是 1 + 右子樹的深度。反之，右子樹為空，左子樹不為空，最小深度是 1 + 左子樹的深度。 最後如果左右子樹都不為空，傳回左右子樹深度最小值 + 1 。