尋找二叉樹(shù)最遠(yuǎn)的葉子結(jié)點(diǎn)(實(shí)例講解)
面試的時(shí)候碰到一個(gè)題：如何找到一個(gè)二叉樹(shù)最遠(yuǎn)的葉子結(jié)點(diǎn)，以及這個(gè)葉子結(jié)點(diǎn)到根節(jié)點(diǎn)的距離？
第一反應(yīng)肯定是遞歸
如何能找到最遠(yuǎn)的葉子結(jié)點(diǎn)，同時(shí)也能記下這個(gè)葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的距離呢？采用一個(gè)List保持從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑就可以了，這個(gè)list的長(zhǎng)度-1就是葉子結(jié)點(diǎn)到根節(jié)點(diǎn)的距離，list的最后一個(gè)結(jié)點(diǎn)就是到葉子結(jié)點(diǎn)
二叉樹(shù)我就不用設(shè)計(jì)了，具體代碼參見(jiàn)我的另一篇文章
/**
* 尋找最遠(yuǎn)的葉子節(jié)點(diǎn)
*/
public void findFarestLeaf() {
List<Node> path = new ArrayList<Node>();
List<Node> longestPath = findLongestPath(root, path);
Node leaf = longestPath.get(longestPath.size() - 1);
System.out.println("最遠(yuǎn)的葉子節(jié)點(diǎn)是<" + leaf.key + ", " + leaf.value + ">，到根節(jié)點(diǎn)的距離是："+(longestPath.size() - 1));
}
public List<Node> findLongestPath(Node x, List<Node> path) {
if (x == null)
return path;
// 每次遞歸必須新建list，要不然會(huì)導(dǎo)致遞歸分支都在同一個(gè)list上面做，實(shí)際是把所有結(jié)點(diǎn)都加入這個(gè)list了
List<Node> currPath = new ArrayList<Node>();
currPath.addAll(path);
currPath.add(x);
List<Node> leftPath = findLongestPath(x.left, currPath);
List<Node> rightPath = findLongestPath(x.right, currPath);
if (leftPath.size() > rightPath.size())
return leftPath;
else
return rightPath;
}
以上這篇尋找二叉樹(shù)最遠(yuǎn)的葉子結(jié)點(diǎn)(實(shí)例講解)就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
相關(guān)文章
IDEA中的Run/Debug Configurations各項(xiàng)解讀
這篇文章主要介紹了IDEA中的Run/Debug Configurations各項(xiàng)解讀,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-09-09
springboot 多環(huán)境配置 yml文件版的實(shí)現(xiàn)方法
這篇文章主要介紹了springboot 多環(huán)境配置 yml文件版的實(shí)現(xiàn)方法,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-06-06
詳解java中的深拷貝和淺拷貝（clone()方法的重寫(xiě)、使用序列化實(shí)現(xiàn)真正的深拷貝）
這篇文章主要介紹了java中的深拷貝和淺拷貝（clone()方法的重寫(xiě)、使用序列化實(shí)現(xiàn)真正的深拷貝），文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03
這篇文章主要為大家詳細(xì)介紹了Java從服務(wù)端下載Excel模板文件的兩種方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08
spring boot 打包jar jar沒(méi)有主目錄清單問(wèn)題的完美解決方法
這篇文章主要介紹了spring boot 打包jar jar沒(méi)有主目錄清單問(wèn)題的解決方法,本文是小編第一次寫(xiě)，希望對(duì)大家有所幫助2018-07-07
可能是全網(wǎng)最詳細(xì)的springboot整合minio教程
MinIO是全球領(lǐng)先的對(duì)象存儲(chǔ)先鋒,在標(biāo)準(zhǔn)硬件上,讀/寫(xiě)速度上高達(dá)183 GB/秒和171 GB/秒,下面這篇文章主要給大家介紹了關(guān)于springboot整合minio的相關(guān)資料，這個(gè)教程可能是全網(wǎng)最詳細(xì)的,需要的朋友可以參考下2022-06-06
五分鐘解鎖springboot admin監(jiān)控新技巧
本文不會(huì)講如何搭建企業(yè)的運(yùn)維監(jiān)控系統(tǒng)，有興趣的可以去找找成熟的比如Zabbix、Prometheus,甚至比較簡(jiǎn)單的Wgcloud都能滿(mǎn)足一定的需求，不在此贅述。本文講解如何使用Springboot admin對(duì)spring boot項(xiàng)目進(jìn)行應(yīng)用監(jiān)控，感興趣的朋友一起看看吧2021-06-06
SpringBoot 二維碼生成base64并上傳OSS的實(shí)現(xiàn)示例
本文主要介紹了SpringBoot 二維碼生成base64并上傳OSS的實(shí)現(xiàn)示例，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05
最近更新了idea2022.2版本，這是一個(gè)比較大的軟件版本更迭，下面小編給大家介紹下idea2022.2?閃退的問(wèn)題及解決方法,需要的朋友可以參考下2022-08-08
這篇文章主要為大家介紹了java響應(yīng)式編程之Reactor使用示例解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-07-07