尋找二叉樹最遠(yuǎn)的葉子結(jié)點(實例講解)

更新時間：2017年12月09日 09:22:43 作者：evasean

下面小編就為大家分享一篇尋找二叉樹最遠(yuǎn)的葉子結(jié)點的實例講解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧

面試的時候碰到一個題：如何找到一個二叉樹最遠(yuǎn)的葉子結(jié)點，以及這個葉子結(jié)點到根節(jié)點的距離？

第一反應(yīng)肯定是遞歸

如何能找到最遠(yuǎn)的葉子結(jié)點，同時也能記下這個葉子節(jié)點到根節(jié)點的距離呢？采用一個List保持從根節(jié)點到葉子節(jié)點的路徑就可以了，這個list的長度-1就是葉子結(jié)點到根節(jié)點的距離，list的最后一個結(jié)點就是到葉子結(jié)點

二叉樹我就不用設(shè)計了，具體代碼參見我的另一篇文章

/**
   * 尋找最遠(yuǎn)的葉子節(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("最遠(yuǎn)的葉子節(jié)點是<" + leaf.key + ", " + leaf.value + ">，到根節(jié)點的距離是："+(longestPath.size() - 1));
  }

  public List<Node> findLongestPath(Node x, List<Node> path) {
    if (x == null)
      return path;
    // 每次遞歸必須新建list，要不然會導(dǎo)致遞歸分支都在同一個list上面做，實際是把所有結(jié)點都加入這個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;
  }

以上這篇尋找二叉樹最遠(yuǎn)的葉子結(jié)點(實例講解)就是小編分享給大家的全部內(nèi)容了，希望能給大家一個參考，也希望大家多多支持腳本之家。

相關(guān)文章

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