当前位置:主页 > java教程 > 二叉树最远的叶子实例分享

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

发布:2019-06-07 14:44:54 170


本站精选了一篇java实例相关的编程文章,网友习元驹根据主题投稿了本篇教程内容,涉及到二叉树、最远、叶子结点、二叉树最远的叶子实例分享相关内容,已被473网友关注,内容中涉及的知识点可以在下方直接下载获取。

二叉树最远的叶子实例分享

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

第一反应肯定是递归

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

 


参考资料

相关文章

  • C++树之遍历二叉树实例详解

    发布:2022-04-11

    这篇文章主要给大家介绍了关于C++树之遍历二叉树的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧


  • Java数据结构之树和二叉树的相关资料

    发布:2023-03-02

    这篇文章主要介绍了Java 数据结构之树和二叉树相关资料,文中通过示例代码和一些相关题目来做介绍,非常详细。对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下!


  • 总结python3实现二叉树的遍历及递归算法

    发布:2020-03-13

    这篇文章主要介绍了python3实现二叉树的遍历与递归算法解析(小结),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习


  • Python简单定义与使用二叉树示例

    发布:2022-07-25

    给大家整理一篇关于Python的教程,这篇文章主要介绍了Python简单定义与使用二叉树,结合实例形式分析了Python定义二叉树及节点插入相关操作技巧,需要的朋友可以参考下


  • C C++ LeetCode题解在二叉树中增加一行示例详解

    发布:2023-03-04

    这篇文章主要为大家介绍了C C++ LeetCode题解在二叉树中增加一行示例详解,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪


  • python 使用turtule绘制递归图形(螺旋、二叉树、谢尔宾斯基三角形)

    python 使用turtule绘制递归图形(螺旋、二叉树、谢尔宾斯基三角形)

    发布:2022-11-07

    为网友们分享了关于python的教程,这篇文章主要介绍了python 使用turtule绘制递归图形(螺旋、二叉树、谢尔宾斯基三角形) ,需要的朋友可以参考下


  • Java实现二叉树的深度优先遍历和广度优先遍历算法示例

    Java实现二叉树的深度优先遍历和广度优先遍历算法示例

    发布:2022-10-18

    为网友们分享了关于Java的教程,这篇文章主要介绍了Java实现二叉树的深度优先遍历和广度优先遍历算法,结合实例形式详细分析了二叉树的定义、深度优先遍历与广度优先遍历算法原理与相关操作实现技巧,需要的朋友可以参考


  • c语言构建一个静态二叉树实现方法

    发布:2022-04-04

    下面小编就为大家带来一篇c语言_构建一个静态二叉树实现方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧


网友讨论