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

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | 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年的文章，迁移过来

请我喝瓶饮料