Fork me on GitHub

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://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来减少垃圾评论。了解我们如何处理您的评论数据