盡管之前你可能做過這道題目,但只要認真看完,相信你會收獲滿滿!可以一起解決如下兩道題目:
- 104.二叉樹的最大深度
- 559.n叉樹的最大深度
104.二叉樹的最大深度
題目地址:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
給定一個二叉樹,找出其最大深度。
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。
說明: 葉子節點是指沒有子節點的節點。
示例:給定二叉樹 [3,9,20,null,null,15,7],
返回它的最大深度 3 。
遞歸法
本題可以使用前序(中左右),也可以使用后序遍歷(左右中),使用前序求的就是深度,使用后序求的是高度。
而根節點的高度就是二叉樹的最大深度,所以本題中我們通過后序求的根節點高度來求的二叉樹最大深度。
這一點其實是很多同學沒有想清楚的,很多題解同樣沒有講清楚。
我先用后序遍歷(左右中)來計算樹的高度。
- 確定遞歸函數的參數和返回值:參數就是傳入樹的根節點,返回就返回這棵樹的深度,所以返回值為int類型。
代碼如下:
intgetdepth(treenode*node)
- 確定終止條件:如果為空節點的話,就返回0,表示高度為0。
代碼如下:
if(node==null)return0;
- 確定單層遞歸的邏輯:先求它的左子樹的深度,再求的右子樹的深度,最后取左右深度最大的數值 再+1 (加1是因為算上當前中間節點)就是目前節點為根節點的樹的深度。
代碼如下:
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));
}
};
精簡之后的代碼根本看不出是哪種遍歷方式,也看不出遞歸三部曲的步驟,所以如果對二叉樹的操作還不熟練,盡量不要直接照著精簡代碼來學。
本題當然也可以使用前序,代碼如下:(充分表現出求深度回溯的過程)
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;
}
};
可以看出使用了前序(中左右)的遍歷順序,這才是真正求深度的邏輯!
注意以上代碼是為了把細節體現出來,簡化一下代碼如下:
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;
}
};
迭代法
使用迭代法的話,使用層序遍歷是最為合適的,因為最大的深度就是二叉樹的層數,和層序遍歷的方式極其吻合。
在二叉樹中,一層一層的來遍歷二叉樹,記錄一下遍歷的層數就是二叉樹的深度,如圖所示:
所以這道題的迭代法就是一道模板題,可以使用二叉樹層序遍歷的模板來解決的。
如果對層序遍歷還不清楚的話,可以看這篇:二叉樹:層序遍歷登場!
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 叉樹,找到其最大深度。
最大深度是指從根節點到最遠葉子節點的最長路徑上的節點總數。
例如,給定一個 3叉樹 :
我們應返回其最大深度,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
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
審核編輯 :李倩
-
C++
+關注
關注
22文章
2108瀏覽量
73623 -
代碼
+關注
關注
30文章
4779瀏覽量
68525 -
二叉樹
+關注
關注
0文章
74瀏覽量
12324
原文標題:看看這些樹的最大深度!
文章出處:【微信號:TheAlgorithm,微信公眾號:算法與數據結構】歡迎添加關注!文章轉載請注明出處。
發布評論請先 登錄
相關推薦
評論