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

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

104.二叉樹的最大深度

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

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

二叉樹的深度為根節(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ì)算樹的高度。

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

代碼如下：

intgetdepth(treenode*node)

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

代碼如下：

if(node==null)return0;

3. 確定單層遞歸的邏輯：先求它的左子樹的深度，再求的右子樹的深度，最后取左右深度最大的數(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/

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

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

例如，給定一個(gè) 3叉樹 :

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

思路：

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

遞歸法

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

104.二叉樹的最大深度

classsolution{
/**
*遞歸法
*/
publicintmaxdepth(treenoderoot){
if(root==null){
return0;
}
intleftdepth=maxdepth(root.left);
intrightdepth=maxdepth(root.right);
returnmath.max(leftdepth,rightdepth)+1;

}
}

classsolution{
/**
*迭代法，使用層序遍歷
*/
publicintmaxdepth(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){
deque.offer(poll.left);
}
if(poll.right!=null){
deque.offer(poll.right);
}
}
}
returndepth;
}
}

python

104.二叉樹的最大深度

遞歸法：

classsolution:
defmaxdepth(self,root:treenode)->int:
returnself.getdepth(root)

defgetdepth(self,node):
ifnotnode:
return0
leftdepth=self.getdepth(node.left)#左
rightdepth=self.getdepth(node.right)#右
depth=1+max(leftdepth,rightdepth)#中
returndepth

遞歸法：精簡代碼

classsolution:
defmaxdepth(self,root:treenode)->int:
ifnotroot:
return0
return1+max(self.maxdepth(root.left),self.maxdepth(root.right))

迭代法：

importcollections
classsolution:
defmaxdepth(self,root:treenode)->int:
ifnotroot:
return0
depth=0#記錄深度
queue=collections.deque()
queue.append(root)
whilequeue:
size=len(queue)
depth+=1
foriinrange(size):
node=queue.popleft()
ifnode.left:
queue.append(node.left)
ifnode.right:
queue.append(node.right)
returndepth

559.n叉樹的最大深度

遞歸法：

classsolution:
defmaxdepth(self,root:'node')->int:
ifnotroot:
return0
depth=0
foriinrange(len(root.children)):
depth=max(depth,self.maxdepth(root.children[i]))
returndepth+1

迭代法：

importcollections
classsolution:
defmaxdepth(self,root:'node')->int:
queue=collections.deque()
ifroot:
queue.append(root)
depth=0#記錄深度
whilequeue:
size=len(queue)
depth+=1
foriinrange(size):
node=queue.popleft()
forjinrange(len(node.children)):
ifnode.children[j]:
queue.append(node.children[j])
returndepth

使用棧來模擬后序遍歷依然可以

classsolution:
defmaxdepth(self,root:'node')->int:
st=[]
ifroot:
st.append(root)
depth=0
result=0
whilest:
node=st.pop()
ifnode!=none:
st.append(node)#中
st.append(none)
depth+=1
foriinrange(len(node.children)):#處理孩子
ifnode.children[i]:
st.append(node.children[i])

else:
node=st.pop()
depth-=1
result=max(result,depth)
returnresult