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