面試的時候碰到一個題：如何找到一個二叉樹最遠的葉子結點，以及這個葉子結點到根節點的距離？
第一反應肯定是遞歸
如何能找到最遠的葉子結點，同時也能記下這個葉子節點到根節點的距離呢？採用一個List保持從根節點到葉子節點的路徑就可以了，這個list的長度-1就是葉子結點到根節點的距離，list的最後一個結點就是到葉子結點
二叉樹我就不用設計了，具體代碼參見我的另一篇文章
/** * 尋找最遠的葉子節點*/ 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("最遠的葉子節點是<" + leaf.key + ", " + leaf.value + ">，到根節點的距離是："+(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; }以上這篇尋找二叉樹最遠的葉子結點(實例講解)就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持武林網。