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