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

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

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

第一反应肯定是递归

如何能找到最远的叶子结点，同时也能记下这个叶子节点到根节点的距离呢？采用一个List保持从根节点到叶子节点的路径就可以了，这个list的长度-1就是叶子结点到根节点的距离，list的最后一个结点就是到叶子结点

二叉树我就不用设计了，具体代码参见我的另一篇文章

/**

* 寻找最远的叶子节点

*/

public void findFarestLeaf() {

List path = 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 findLongestPahttp://th(Nhttp://ode x, List path) {

if (x == null)miMWNV

return path;

// 每次递归必须新建list，要不然会导致递归分支都在同一个list上面做，实际是把所有结点都加入这个list了

List currPath = new ArrayList();

currPath.addAll(path);miMWNV

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;

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。