盡管之前你可能做過這道題目，但只要認(rèn)真看完，相信你會收獲滿滿！可以一起解決如下兩道題目：

104.二叉樹的最大深度
559.n叉樹的最大深度

104.二叉樹的最大深度

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

給定一個二叉樹，找出其最大深度。

二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)。

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

示例：給定二叉樹 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

遞歸法

本題可以使用前序（中左右），也可以使用后序遍歷（左右中），使用前序求的就是深度，使用后序求的是高度。

而根節(jié)點(diǎn)的高度就是二叉樹的最大深度，所以本題中我們通過后序求的根節(jié)點(diǎn)高度來求的二叉樹最大深度。

這一點(diǎn)其實(shí)是很多同學(xué)沒有想清楚的，很多題解同樣沒有講清楚。

我先用后序遍歷（左右中）來計(jì)算樹的高度。

確定遞歸函數(shù)的參數(shù)和返回值：參數(shù)就是傳入樹的根節(jié)點(diǎn)，返回就返回這棵樹的深度，所以返回值為int類型。

代碼如下：

intgetdepth(treenode*node)

確定終止條件：如果為空節(jié)點(diǎn)的話，就返回0，表示高度為0。

代碼如下：

if(node==null)return0;

確定單層遞歸的邏輯：先求它的左子樹的深度，再求的右子樹的深度，最后取左右深度最大的數(shù)值再+1 （加1是因?yàn)樗闵袭?dāng)前中間節(jié)點(diǎn)）就是目前節(jié)點(diǎn)為根節(jié)點(diǎn)的樹的深度。

代碼如下：

intleftdepth=getdepth(node->left);//左
intrightdepth=getdepth(node->right);//右
intdepth=1+max(leftdepth,rightdepth);//中
returndepth;

所以整體c++代碼如下：

classsolution{
public:
intgetdepth(treenode*node){
if(node==null)return0;
intleftdepth=getdepth(node->left);//左
intrightdepth=getdepth(node->right);//右
intdepth=1+max(leftdepth,rightdepth);//中
returndepth;
}
intmaxdepth(treenode*root){
returngetdepth(root);
}
};

代碼精簡之后c++代碼如下：

classsolution{
public:
intmaxdepth(treenode*root){
if(root==null)return0;
return1+max(maxdepth(root->left),maxdepth(root->right));
}
};

精簡之后的代碼根本看不出是哪種遍歷方式，也看不出遞歸三部曲的步驟，所以如果對二叉樹的操作還不熟練，盡量不要直接照著精簡代碼來學(xué)。

本題當(dāng)然也可以使用前序，代碼如下：(充分表現(xiàn)出求深度回溯的過程)

classsolution{
public:
intresult;
voidgetdepth(treenode*node,intdepth){
result=depth>result?depth:result;//中

if(node->left==null&&node->right==null)return;

if(node->left){//左
depth++;//深度+1
getdepth(node->left,depth);
depth--;//回溯，深度-1
}
if(node->right){//右
depth++;//深度+1
getdepth(node->right,depth);
depth--;//回溯，深度-1
}
return;
}
intmaxdepth(treenode*root){
result=0;
if(root==0)returnresult;
getdepth(root,1);
returnresult;
}
};

可以看出使用了前序（中左右）的遍歷順序，這才是真正求深度的邏輯！

注意以上代碼是為了把細(xì)節(jié)體現(xiàn)出來，簡化一下代碼如下：

classsolution{
public:
intresult;
voidgetdepth(treenode*node,intdepth){
result=depth>result?depth:result;//中
if(node->left==null&&node->right==null)return;
if(node->left){//左
getdepth(node->left,depth+1);
}
if(node->right){//右
getdepth(node->right,depth+1);
}
return;
}
intmaxdepth(treenode*root){
result=0;
if(root==0)returnresult;
getdepth(root,1);
returnresult;
}
};

迭代法

使用迭代法的話，使用層序遍歷是最為合適的，因?yàn)樽畲蟮纳疃染褪嵌鏄涞膶訑?shù)，和層序遍歷的方式極其吻合。

在二叉樹中，一層一層的來遍歷二叉樹，記錄一下遍歷的層數(shù)就是二叉樹的深度，如圖所示：

所以這道題的迭代法就是一道模板題，可以使用二叉樹層序遍歷的模板來解決的。

如果對層序遍歷還不清楚的話，可以看這篇：二叉樹：層序遍歷登場！

c++代碼如下：

classsolution{
public:
intmaxdepth(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);
}
}
returndepth;
}
};

那么我們可以順便解決一下n叉樹的最大深度問題

559.n叉樹的最大深度

題目地址：https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/

給定一個 n 叉樹，找到其最大深度。

最大深度是指從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)總數(shù)。

例如，給定一個 3叉樹 :

我們應(yīng)返回其最大深度，3。

思路：

依然可以提供遞歸法和迭代法，來解決這個問題，思路是和二叉樹思路一樣的，直接給出代碼如下：

遞歸法

c++代碼：

classsolution{
public:
intmaxdepth(node*root){
if(root==0)return0;
intdepth=0;
for(inti=0;ichildren.size();i++){
depth=max(depth,maxdepth(root->children[i]));
}
returndepth+1;
}
};

迭代法

依然是層序遍歷，代碼如下：

classsolution{
public:
intmaxdepth(node*root){
queueque;
if(root!=null)que.push(root);
intdepth=0;
while(!que.empty()){
intsize=que.size();
depth++;//記錄深度
for(inti=0;ifor(intj=0;jchildren.size();j++){
if(node->children[j])que.push(node->children[j]);
}
}
}
returndepth;
}
};

其他語言版本

java