这篇文章将为大家详细讲解有关如何寻找二叉树最远的叶子结点,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。
十载的祁门网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。全网整合营销推广的优势是能够根据用户设备显示端的尺寸不同,自动调整祁门建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。创新互联从事“祁门网站设计”,“祁门网站推广”以来,每个客户项目都认真落实执行。
第一反应肯定是递归
如何能找到最远的叶子结点,同时也能记下这个叶子节点到根节点的距离呢?采用一个List保持从根节点到叶子节点的路径就可以了,这个list的长度-1就是叶子结点到根节点的距离,list的最后一个结点就是到叶子结点
二叉树我就不用设计了
/** * 寻找最远的叶子节点 */ public void findFarestLeaf() { Listpath = new ArrayList (); List longestPath = findLongestPath(root, path); Node leaf = longestPath.get(longestPath.size() - 1); System.out.println("最远的叶子节点是<" + leaf.key + ", " + leaf.value + ">,到根节点的距离是:"+(longestPath.size() - 1)); } public List findLongestPath(Node x, List path) { if (x == null) return path; // 每次递归必须新建list,要不然会导致递归分支都在同一个list上面做,实际是把所有结点都加入这个list了 List currPath = new ArrayList (); currPath.addAll(path); currPath.add(x); List leftPath = findLongestPath(x.left, currPath); List rightPath = findLongestPath(x.right, currPath); if (leftPath.size() > rightPath.size()) return leftPath; else return rightPath; }
关于“如何寻找二叉树最远的叶子结点”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。