Java語(yǔ)言描述二叉樹的深度和寬度
解釋：
二叉樹的深度：從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過(guò)的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹的一條路徑，最長(zhǎng)路徑的長(zhǎng)度為樹的深度。
二叉樹的寬度：二叉樹的每一層中都有一定數(shù)量的節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)最多的那一層的節(jié)點(diǎn)數(shù)叫做二叉樹的寬度。
思路：遞歸實(shí)現(xiàn)。
1.每個(gè)節(jié)點(diǎn)都可以看作根節(jié)點(diǎn)
2.根節(jié)點(diǎn)（任意一個(gè)節(jié)點(diǎn)）的深度等于它的左子樹或右子樹深度最大值+1
3.從根結(jié)點(diǎn)開始遍歷，若遍歷到葉子節(jié)點(diǎn)，深度為0
//二叉樹的深度
public static int Depth(node root){
if(root == null){
return 0;
}
int dl = Depth(root.leftchild);
int dr = Depth(root.rightchild);
return dl>dr? dl+1:dr+1;
}
二、二叉樹的寬度
思路：層序遍歷時(shí)添加一個(gè)計(jì)數(shù)器，記錄每層的節(jié)點(diǎn)數(shù)
1.每層出隊(duì)列時(shí)記錄下一層的節(jié)點(diǎn)數(shù)，其實(shí)就是隊(duì)列的Size()
2.每層遍歷結(jié)束時(shí)，比較最大寬度與當(dāng)前層節(jié)點(diǎn)數(shù)，記錄最大值
public static int Width(node root) {
if(root == null)
return 0;
Queue<node> q = new LinkedList<node>();
q.add(root);
int width = 1;
//最大寬度
int len = 1;
//當(dāng)前層節(jié)點(diǎn)數(shù)
while(q.size()>0){
while(len-->0){
node node = q.poll();
if(node.leftchild != null){
q.add(node.leftchild);
}
if(node.rightchild != null){
q.add(node.rightchild);
}
}
len = q.size();
//每層循環(huán)結(jié)束后記錄下一層的節(jié)點(diǎn)數(shù)
width = width>q.size() ? width : q.size();
}
return width;
}
總結(jié)
以上就是本文關(guān)于Java語(yǔ)言描述二叉樹的深度和寬度的全部?jī)?nèi)容，希望對(duì)大家有所幫助。如有不足之處，歡迎留言指出。感謝朋友們對(duì)本站的支持！
- java實(shí)現(xiàn)二叉樹的創(chuàng)建及5種遍歷方法(總結(jié))
- Java實(shí)現(xiàn)求二叉樹的深度和寬度
- java使用歸并刪除法刪除二叉樹中節(jié)點(diǎn)的方法
- Java實(shí)現(xiàn)二叉樹的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法示例
- Java實(shí)現(xiàn)打印二叉樹所有路徑的方法
- Java的二叉樹排序以及遍歷文件展示文本格式的文件樹
- Java實(shí)現(xiàn)的二叉樹常用操作【前序建樹，前中后遞歸非遞歸遍歷及層序遍歷】
- java編程求二叉樹最大路徑問(wèn)題代碼分析
- Java完全二叉樹的創(chuàng)建與四種遍歷方法分析
- Java中二叉樹的建立和各種遍歷實(shí)例代碼
- Java實(shí)現(xiàn)二叉樹的建立、計(jì)算高度與遞歸輸出操作示例
相關(guān)文章
Mybatis Plus整合PageHelper分頁(yè)的實(shí)現(xiàn)示例
這篇文章主要介紹了Mybatis Plus整合PageHelper分頁(yè)的實(shí)現(xiàn)示例，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
本文主要介紹了java 單例模式，單例對(duì)象（Singleton）是一種常用的設(shè)計(jì)模式。在Java應(yīng)用中，單例對(duì)象能保證在一個(gè)JVM中，該對(duì)象只有一個(gè)實(shí)例存在,希望能幫助有需要的同學(xué)2016-07-07
細(xì)心的小伙伴可能會(huì)發(fā)現(xiàn)，抖音新上線了 IP 屬地的功能，小伙伴在發(fā)表動(dòng)態(tài)、發(fā)表評(píng)論以及聊天的時(shí)候，都會(huì)顯示自己的 IP 屬地信息，本篇文章我們來(lái)模擬實(shí)現(xiàn)這一功能2022-07-07
springBoot整合shiro如何解決讀取不到@value值問(wèn)題
這篇文章主要介紹了springBoot整合shiro如何解決讀取不到@value值問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,2023-08-08
java?面向?qū)ο蟠a塊及不同位置對(duì)屬性賦值的執(zhí)行順序
這篇文章主要介紹了java面向?qū)ο蟠a塊及不同位置對(duì)屬性賦值的執(zhí)行順序，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-09-09
這篇文章主要介紹了關(guān)于springboot配置文件密文解密方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-08-08
這篇文章主要介紹了使用SpringMVC接收文件流上傳和表單參數(shù)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-02-02
這篇文章主要介紹了Java中的字符串類型,需要的朋友可以參考下2014-02-02
Spring多數(shù)據(jù)源切換失敗,發(fā)現(xiàn)與事務(wù)相關(guān)問(wèn)題
這篇文章主要介紹了Spring多數(shù)據(jù)源切換失敗,發(fā)現(xiàn)與事務(wù)相關(guān)問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-01-01
java實(shí)現(xiàn)時(shí)間控制的幾種方案
這篇文章主要介紹了java實(shí)現(xiàn)時(shí)間控制的幾種方案,本文從多個(gè)方面給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2019-07-07