和求最大深度一個(gè)套路？

111.二叉樹(shù)的最小深度

題目地址：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

給定一個(gè)二叉樹(shù)，找出其最小深度。

最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。

說(shuō)明:葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例:

給定二叉樹(shù)[3,9,20,null,null,15,7],

返回它的最小深度 2.

思路

看完了這篇104.二叉樹(shù)的最大深度，再來(lái)看看如何求最小深度。

直覺(jué)上好像和求最大深度差不多，其實(shí)還是差不少的。

遍歷順序上依然是后序遍歷（因?yàn)橐容^遞歸返回之后的結(jié)果），但在處理中間節(jié)點(diǎn)的邏輯上，最大深度很容易理解，最小深度可有一個(gè)誤區(qū)，如圖：

這就重新審題了，題目中說(shuō)的是：最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。，注意是葉子節(jié)點(diǎn)。

什么是葉子節(jié)點(diǎn)，左右孩子都為空的節(jié)點(diǎn)才是葉子節(jié)點(diǎn)！

遞歸法

來(lái)來(lái)來(lái)，一起遞歸三部曲：

1. 確定遞歸函數(shù)的參數(shù)和返回值

參數(shù)為要傳入的二叉樹(shù)根節(jié)點(diǎn)，返回的是int類型的深度。

代碼如下：

intgetDepth(TreeNode*node)

2. 確定終止條件

終止條件也是遇到空節(jié)點(diǎn)返回0，表示當(dāng)前節(jié)點(diǎn)的高度為0。

代碼如下：

if(node==NULL)return0;

3. 確定單層遞歸的邏輯

這塊和求最大深度可就不一樣了，一些同學(xué)可能會(huì)寫(xiě)如下代碼：

intleftDepth=getDepth(node->left);
intrightDepth=getDepth(node->right);
intresult=1+min(leftDepth,rightDepth);
returnresult;

這個(gè)代碼就犯了此圖中的誤區(qū)：

如果這么求的話，沒(méi)有左孩子的分支會(huì)算為最短深度。

所以，如果左子樹(shù)為空，右子樹(shù)不為空，說(shuō)明最小深度是 1 + 右子樹(shù)的深度。

反之，右子樹(shù)為空，左子樹(shù)不為空，最小深度是 1 + 左子樹(shù)的深度。最后如果左右子樹(shù)都不為空，返回左右子樹(shù)深度最小值 + 1 。

代碼如下：

intleftDepth=getDepth(node->left);//左
intrightDepth=getDepth(node->right);//右
//中
//當(dāng)一個(gè)左子樹(shù)為空，右不為空，這時(shí)并不是最低點(diǎn)
if(node->left==NULL&&node->right!=NULL){
return1+rightDepth;
}
//當(dāng)一個(gè)右子樹(shù)為空，左不為空，這時(shí)并不是最低點(diǎn)
if(node->left!=NULL&&node->right==NULL){
return1+leftDepth;
}
intresult=1+min(leftDepth,rightDepth);
returnresult;

遍歷的順序?yàn)楹笮颍ㄗ笥抑校?，可以看出?strong>求二叉樹(shù)的最小深度和求二叉樹(shù)的最大深度的差別主要在于處理左右孩子不為空的邏輯。

整體遞歸代碼如下：

classSolution{
public:
intgetDepth(TreeNode*node){
if(node==NULL)return0;
intleftDepth=getDepth(node->left);//左
intrightDepth=getDepth(node->right);//右
//中
//當(dāng)一個(gè)左子樹(shù)為空，右不為空，這時(shí)并不是最低點(diǎn)
if(node->left==NULL&&node->right!=NULL){
return1+rightDepth;
}
//當(dāng)一個(gè)右子樹(shù)為空，左不為空，這時(shí)并不是最低點(diǎn)
if(node->left!=NULL&&node->right==NULL){
return1+leftDepth;
}
intresult=1+min(leftDepth,rightDepth);
returnresult;
}

intminDepth(TreeNode*root){
returngetDepth(root);
}
};

精簡(jiǎn)之后代碼如下：

classSolution{
public:
intminDepth(TreeNode*root){
if(root==NULL)return0;
if(root->left==NULL&&root->right!=NULL){
return1+minDepth(root->right);
}
if(root->left!=NULL&&root->right==NULL){
return1+minDepth(root->left);
}
return1+min(minDepth(root->left),minDepth(root->right));
}
};

精簡(jiǎn)之后的代碼根本看不出是哪種遍歷方式，所以依然還要強(qiáng)調(diào)一波：如果對(duì)二叉樹(shù)的操作還不熟練，盡量不要直接照著精簡(jiǎn)代碼來(lái)學(xué)。

迭代法

相對(duì)于104.二叉樹(shù)的最大深度，本題還可以使用層序遍歷的方式來(lái)解決，思路是一樣的。

如果對(duì)層序遍歷還不清楚的話，可以看這篇：二叉樹(shù)：層序遍歷登場(chǎng)！

需要注意的是，只有當(dāng)左右孩子都為空的時(shí)候，才說(shuō)明遍歷的最低點(diǎn)了。如果其中一個(gè)孩子為空則不是最低點(diǎn)

代碼如下：（詳細(xì)注釋）

classSolution{
public:

intminDepth(TreeNode*root){
if(root==NULL)return0;
intdepth=0;
queueque;
que.push(root);
while(!que.empty()){
intsize=que.size();
depth++;//記錄最小深度
for(inti=0;iif(node->left)que.push(node->left);
if(node->right)que.push(node->right);
if(!node->left&&!node->right){//當(dāng)左右孩子都為空的時(shí)候，說(shuō)明是最低點(diǎn)的一層了，退出
returndepth;
}
}
}
returndepth;
}
};

其他語(yǔ)言版本

Java

classSolution{
/**
*遞歸法，相比求MaxDepth要復(fù)雜點(diǎn)
*因?yàn)樽钚∩疃仁菑母?jié)點(diǎn)到最近**葉子節(jié)點(diǎn)**的最短路徑上的節(jié)點(diǎn)數(shù)量
*/
publicintminDepth(TreeNoderoot){
if(root==null){
return0;
}
intleftDepth=minDepth(root.left);
intrightDepth=minDepth(root.right);
if(root.left==null){
returnrightDepth+1;
}
if(root.right==null){
returnleftDepth+1;
}
//左右結(jié)點(diǎn)都不為null
returnMath.min(leftDepth,rightDepth)+1;
}
}

classSolution{
/**
*迭代法，層序遍歷
*/
publicintminDepth(TreeNoderoot){
if(root==null){
return0;
}
Dequedeque=newLinkedList<>();
deque.offer(root);
intdepth=0;
while(!deque.isEmpty()){
intsize=deque.size();
depth++;
for(inti=0;iif(poll.left==null&&poll.right==null){
//是葉子結(jié)點(diǎn)，直接返回depth，因?yàn)閺纳贤卤闅v，所以該值就是最小值
returndepth;
}
if(poll.left!=null){
deque.offer(poll.left);
}
if(poll.right!=null){
deque.offer(poll.right);
}
}
}
returndepth;
}
}

Python

遞歸法：

classSolution:
defminDepth(self,root:TreeNode)->int:
ifnotroot:
return0
ifnotroot.leftandnotroot.right:
return1

min_depth=10**9
ifroot.left:
min_depth=min(self.minDepth(root.left),min_depth)#獲得左子樹(shù)的最小高度
ifroot.right:
min_depth=min(self.minDepth(root.right),min_depth)#獲得右子樹(shù)的最小高度
returnmin_depth+1

迭代法：

classSolution:
defminDepth(self,root:TreeNode)->int:
ifnotroot:
return0
que=deque()
que.append(root)
res=1

whileque:
for_inrange(len(que)):
node=que.popleft()
#當(dāng)左右孩子都為空的時(shí)候，說(shuō)明是最低點(diǎn)的一層了，退出
ifnotnode.leftandnotnode.right:
returnres
ifnode.leftisnotNone:
que.append(node.left)
ifnode.rightisnotNone:
que.append(node.right)
res+=1
returnres

審核編輯 ：李倩