寻找二叉树最远的叶子结点(实例讲解)
面试的时候碰到一个题:如何找到一个二叉树最远的叶子结点,以及这个叶子结点到根节点的距离?
第一反应肯定是递归
如何能找到最远的叶子结点,同时也能记下这个叶子节点到根节点的距离呢?采用一个List保持从根节点到叶子节点的路径就可以了,这个list的长度-1就是叶子结点到根节点的距离,list的最后一个结点就是到叶子结点
二叉树我就不用设计了,具体代码参见我的另一篇文章
/** *寻找最远的叶子节点 */ publicvoidfindFarestLeaf(){ Listpath=newArrayList (); List longestPath=findLongestPath(root,path); Nodeleaf=longestPath.get(longestPath.size()-1); System.out.println("最远的叶子节点是<"+leaf.key+","+leaf.value+">,到根节点的距离是:"+(longestPath.size()-1)); } publicList findLongestPath(Nodex,List path){ if(x==null) returnpath; //每次递归必须新建list,要不然会导致递归分支都在同一个list上面做,实际是把所有结点都加入这个list了 List currPath=newArrayList (); currPath.addAll(path); currPath.add(x); List leftPath=findLongestPath(x.left,currPath); List rightPath=findLongestPath(x.right,currPath); if(leftPath.size()>rightPath.size()) returnleftPath; else returnrightPath; }
以上这篇寻找二叉树最远的叶子结点(实例讲解)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持毛票票。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。