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

面试的时候碰到一个题：如何找到一个二叉树最远的叶子结点，以及这个叶子结点到根节点的距离？

第一反应肯定是递归

如何能找到最远的叶子结点，同时也能记下这个叶子节点到根节点的距离呢？采用一个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;
  }

以上这篇寻找二叉树最远的叶子结点(实例讲解)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持。