版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | http://vearne.cc

题目

求二叉树两个距离最远的叶子节点?

分析

首先我们分析一下距离最远的叶子节点都产生在什么位置
情况1:

显然距离最远的两个节点是节点3和5,距离是4

情况2:

对于情况2,如果我们观察以节点0为根的树,我们发现距离最远的叶子节点是7和8,距离是6,最远节点出现在左子树,而节点2距离节点7和8的距离是5。同理我们可以画出最远距离出现在右子树的情况。

由上面的情况,我们可以知道
由分治法的思想,我们可以想到 最远距离叶子节点只能出现在
A. 出现在左子树
B. 出现在右子树
C. 两个节点分别位于左右子树
很容易想到满足此种遍历顺序的是后序遍历。
每次遍历的时候需要做如下操作:

1.记录左子树中,到根节点最远的叶子节点编号N1,以及到根的距离L1,此子树中最远距离的两个叶子节点t1、t2,以及它们的距离D1

1.记录右子树中,到根节点最远的叶子节点编号N2,以及到根的距离L2,此子树中最远距离的两个叶子节点t3、t4,以及它们的距离D2

2.当访问到根节点时,需要计算一下前面提到情况C 有没有出现。

此种情况计算起来非常简单,如果左右子树都存在,那么左子树中叶子节点到根的最远距离是 L1 +1 , 右子树中叶子节点到根的最远距离是 L2 +1, 那么情况C 下的距离是 L1 + L2 + 2

比较这三种情况哪种最大即可

后记

2012年的文章,迁移过来


如果我的文章对你有帮助,你可以给我打赏以促使我拿出更多的时间和精力来分享我的经验和思考总结。

微信支付码

发表评论

电子邮件地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据