尋找二叉樹(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)文章
MyBatis-Plus提供了多種方式來(lái)配置SQL打印功能,以便進(jìn)行調(diào)試和性能分析,這篇文章主要介紹了mybatisPlus打印sql配置的四種方法,文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-12-12
jvm添加自定義dns實(shí)現(xiàn)過(guò)程示例
這篇文章主要為大家介紹了jvm添加自定義dns實(shí)現(xiàn)過(guò)程示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-08-08
在本篇文章中小編給大家分享了關(guān)于Java標(biāo)識(shí)接口的使用方法和教程內(nèi)容，有需要的朋友們學(xué)習(xí)下。2019-01-01
Java使用JNDI連接數(shù)據(jù)庫(kù)的實(shí)現(xiàn)方法
本文主要介紹了Java使用JNDI連接數(shù)據(jù)庫(kù)的實(shí)現(xiàn)方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-12-12
spring?boot?executable?jar/war?原理解析
spring boot里其實(shí)不僅可以直接以 java -jar demo.jar的方式啟動(dòng)，還可以把jar/war變?yōu)橐粋€(gè)可以執(zhí)行的腳本來(lái)啟動(dòng)，比如./demo.jar，這篇文章主要介紹了spring?boot?executable?jar/war?原理,需要的朋友可以參考下2023-02-02
spring中的@Value讀取配置文件的細(xì)節(jié)處理過(guò)程
這篇文章主要介紹了spring中的@Value讀取配置文件的細(xì)節(jié)處理過(guò)程,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-09-09
springcloud使用Hystrix進(jìn)行微服務(wù)降級(jí)管理
這篇文章主要介紹了springcloud使用Hystrix進(jìn)行微服務(wù)降級(jí)管理，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
基于Java中進(jìn)制的轉(zhuǎn)換函數(shù)詳解
下面小編就為大家?guī)?lái)一篇基于Java中進(jìn)制的轉(zhuǎn)換函數(shù)詳解。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-07-07
Spring boot監(jiān)控Actuator-Admin實(shí)現(xiàn)過(guò)程詳解
這篇文章主要介紹了Spring boot監(jiān)控Actuator-Admin實(shí)現(xiàn)過(guò)程詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-09-09
Storm框架中的每個(gè)Spout和Bolt都相當(dāng)于獨(dú)立的應(yīng)用，Strom在啟動(dòng)spout和bolt時(shí)提供了一個(gè)open方法(spout)和prepare方法(bolt)。這篇文章主要介紹了Storm框架整合springboot的方法,需要的朋友可以參考下2018-11-11