如何尋找二叉樹最遠的葉子結(jié)點

這篇文章將為大家詳細講解有關(guān)如何尋找二叉樹最遠的葉子結(jié)點，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

第一反應肯定是遞歸

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

二叉樹我就不用設計了

/**
   * 尋找最遠的葉子節(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上面做，實際是把所有結(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;
  }

關(guān)于“如何尋找二叉樹最遠的葉子結(jié)點”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。