证明树的任何一个最深结点必然为树的一条最长简单路径的端点

源自该题:

力扣

证明树的任何一个最深结点必然为树的一条最长简单路径的端点这一命题

(情况1)首先假设某条最长简单路径经过树的根结点,那么此时该路径的长度为根结点左子树部分路径长度+右子树部分路径长度,显然,无论指定的最深结点在根结点的左子树还是右子树,都能为对应的子树提供最长的部分路径,因此在此种情况下,命题成立。

然后考虑更一般的情况:(情况2)某条最长简单路径经过树中的某个非根结点且以该点为中心,若指定的最深结点属于该结点的某个子树,则情况类似于上述最简单的情况,此时,命题显然成立。

而若指定的最深结点不属于该结点的某个子树,

(情况3)假设该子树中不存在任意最深结点

考虑由该结点构成的简单路径的左半部分和右半部分长度分别为l和r,该结点到树的根结点的距离为x,根结点到最深结点的距离为y,这里假设l <= r,l > r情况类似,那么此时,显然,(x + l) < y,因此l < y,因此l < (y + x),即,从最深结点到达根结点再到达该结点然后连接右子树的部分路径的长度要比原先的路径更长,因此这种情况是不存在的。

(情况4)假设该子树中存在最深结点,

那么,根据情况2可知,该结点一定在最长简单路径上,与处理情况3的方法类似 ,若l < r,l > r情况类似,那么此时,显然(x + l) < y,这种情况类似于情况3,因此l < r这种情况不存在,l > r同理,那么考虑l=r的情况,此时显然(x + l) = y,那么l = y - x < y + x,很显然,此种情况同样不存在。

综上所述,原命题成立,同时还可以得出如下结论:

若某条最长简单路径经过树中的某个结点且以该点为中心,则所有的最深结点一定属于该子树。

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

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