寻找二叉树最远的叶子结点(实例讲解)

/**
   * 寻找最远的叶子节点
   */
  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;
  }