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

2024-09-27 01:55:15

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

第一反应肯定是递归

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

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

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

面试的时候碰到一个题:如何找到一个二叉树最远的叶子结点,以及这个叶子结点到根节点的距离? 第一反应肯定是递归如何能找到最远的叶子结点,同时也能记下这个叶子节点到根节点的距离呢?采用一个List保持从根节点到叶子节点的路径就可以了,这个list的长度-1就是叶子结点到根节点的距离,list的最后一个结点就是到叶子结点二叉树我就不用设计了,具体代码参见我的另一篇文章 /** * 寻找最远的叶子节点 */ public void findFarestLeaf() { List<Node> pat
统计C语言二叉树中叶子结点个数

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的,下面我们就用简单小栗子来简单说明关于统计C语言二叉树中叶子结点个数的方法吧简单小栗子: #include<stdio.h> #include<stdlib.h> typedef char ElemType; typedef struct BTNode { ElemType data; struct B
python之tensorflow手把手实例讲解斑马线识别实现

一,斑马线的数据集数据集的构成: test train zebra corssing:56 zebra corssing:168 other:54 other:164 二,代码部分 1.导包 import tensorflow as tf from tensorflow.keras.preprocessing.image import ImageDataGenerator import numpy as np import matplotlib.pyplot as plt import ker
python爬虫正则表达式使用技巧及爬取个人博客的实例讲解

这篇博客是自己<数据挖掘与分析>课程讲到正则表达式爬虫的相关内容,主要简单介绍Python正则表达式爬虫,同时讲述常见的正则表达式分析方法,最后通过实例爬取作者的个人博客网站.希望这篇基础文章对您有所帮助,如果文章中存在错误或不足之处,还请海涵.真的太忙了,太长时间没有写博客了,抱歉~ 一.正则表达式正则表达式(Regular Expression,简称Regex或RE)又称为正规表示法或常规表示法,常常用来检索.替换那些符合某个模式的文本,它首先设定好了一些特殊的字及字符组合,通过组合的&
打造通用的匀速运动框架(实例讲解)

本文,是接着上基于匀速运动的实例讲解(侧边栏,淡入淡出) 继续的,在这篇文章的最后,我们做了2个小实例:侧边栏与改变透明度的淡入淡出效果,本文我们把上文的animate函数,继续改造,让他变得更加的通用和强大: 1,支持多个物体的运动 2,同时运动 3,顺序运动这三种运动方式也是jquery中animate函数支持的一.animate函数中怎么区分变化不同的样式? 上文中,侧边栏效果用的animate函数改变的是left值 function animate(obj, target, s
python数据结构链表之单向链表(实例讲解)

单向链表单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域.这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值. 表元素域elem用来存放具体的数据. 链接域next用来存放下一个节点的位置(python中的标识) 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点. 节点实现 class Node(object): """单链表的结点""" def __i
用 Python 爬了爬自己的微信朋友(实例讲解)

最近几天干啥都不来劲,昨晚偶然了解到 Python 里的 itchat 包,它已经完成了 wechat 的个人账号 API 接口,使爬取个人微信信息更加方便.鉴于自己很早之前就想知道诸如自己微信好友性别比例都来自哪个城市之类的问题,于是乎玩心一起,打算爬一下自己的微信. 作者:Alfred 首先,在终端安装一下 itchat 包. 安装完成后导入包,再登陆自己的微信.过程中会生产一个登陆二维码,扫码之后即可登陆.登陆成功后,把自己好友的相关信息爬下来. 有了上面的 friends 数据,我们就可
SPFA 算法实例讲解

适用范围:给定的图存在负权边,这时类似Dijkstra等算法便没有了用武之地,而Bellman-Ford算法的复杂度又过高,SPFA算法便派上用场了. 我们约定有向加权图G不存在负权回路,即最短路径一定存在.当然,我们可以在执行该算法前做一次拓扑排序,以判断是否存在负权回路,但这不是我们讨论的重点. 算法思想:我们用数组d记录每个结点的最短路径估计值,用邻接表来存储图G.我们采取的方法是动态逼近法:设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路
Java实现Web应用中的定时任务(实例讲解)

定时任务,是指定一个未来的时间范围执行一定任务的功能.在当前WEB应用中,多数应用都具备任务调度功能,针对不同的语音,不同的操作系统, 都有其自己的语法及解决方案,windows操作系统把它叫做任务计划,linux中cron服务都提供了这个功能,在我们开发业务系统中很多时候会涉及到这个功能.本场chat将使用java语言完成日常开发工作中常用定时任务的使用,希望给大家工作及学习带来帮助. 一.定时任务场景 (1)驱动处理工作流程作为一个新的预支付订单被初始化放置,如果该订单在指定时间内未进行支
在Windows中设置Python环境变量的实例讲解

在 Windows 设置环境变量在环境变量中添加Python目录: 在命令提示框中(cmd) : 输入 path=%path%;C:\Python 按下"Enter". 注意: C:\Python 是Python的安装目录. 也可以通过以下方式设置: • 右键点击"计算机",然后点击"属性" • 然后点击"高级系统设置" • 选择"系统变量"窗口下面的"Path",双击即可! • 然后

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

相关推荐

随机推荐