面试的时候碰到一个题:如何找到一个二叉树最远的叶子结点,以及这个叶子结点到根节点的距离?
第一反应肯定是递归
如何能找到最远的叶子结点,同时也能记下这个叶子节点到根节点的距离呢?采用一个List保持从根节点到叶子节点的路径就可以了,这个list的长度-1就是叶子结点到根节点的距离,list的最后一个结点就是到叶子结点
二叉树我就不用设计了,具体代码参见我的另一篇文章
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
/**
* 寻找最远的叶子节点
*/
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;
}
|
以上这篇寻找二叉树最远的叶子结点(实例讲解)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持服务器之家。
原文链接:http://www.cnblogs.com/evasean/p/7999902.html