首页 > 试题广场 >

二叉树节点间的最大距离问题

[编程题]二叉树节点间的最大距离问题

从二叉树的节点 A 出发，可以向上或者向下走，但沿途的节点只能经过一次，当到达节点 B 时，路径上的节点数叫作 A 到 B 的距离。

现在给出一棵二叉树，求整棵树上每对节点之间的最大距离。

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)
最后一行为节点 o1 和 o2。

输出一个整数表示答案。

示例1

输入

算法知识视频讲解

我要出去乱说

发表于 2022-07-01 10:49:58

1、思路树形DP套路第一步：分析答案来自哪些可能性： 1、以root为头节点的子树，最大距离可能是左子树上的最大距离； 2、以root为头节点的子树，最大距离可能是右子树上的最大距离； 3、以root为头节点的子树，最大距离可能是左子树上高度 + 右子树高度 + 1（root节点本身展开全文

keepgoing20190801113019

发表于 2019-08-04 00:59:04

求最大距离的方法从左右子树的高度入手。从根结点看，左子树上距根结点最远的结点到根结点的距离应为左子树的树高+1，右子树同理，那么左子树上存在至少一个结点往根这条路径加上根到右子树上至少某一个结点的距离为左子树高度+右子树高度+1；但这并不一定就是所有跟离中最远的，比如可以假设某个子结展开全文

树

上传者：小小

难度：

10条回答 23收藏 8103浏览

查看代码

二叉树节点间的最大距离问题

扫一扫，把题目装进口袋