狗狗 昂赛

最后一题，因为给定的是树，所以可以充分利用这个结构，首先求出以每个节点为根形成的子树中的所有节点的个数
然后选定根节点，计算从根节点到所有其他节点的总距离，然后深搜向下走，每走一步，可以计算出来总距离变化了多少，找到这个最小值就可以了
这个方法要对整棵树遍历两遍（或三遍，看实现），时间复杂度应该就是O(n)的，理论上没有更好的解法了吧

byrlhb 发表于 2018-5-1 09:30
仔细想一下，第五题其实就是leetcode里面那个求树的depth最小的根那个题

你是个天才

byrlhb 发表于 2018-5-1 09:30
仔细想一下，第五题其实就是leetcode里面那个求树的depth最小的根那个题

求具体题号？

第二题能讲的详细点吗

楼主你好， 第一题的第二问还是不太明白什么意思。。 第二题能举个例子吗？

对于第五题， 我的想法是， 对于一棵树， 任意两个点有唯一的路径， 那么对树进行一次遍历可以得到任意两个点之间的距离， 这样就得到了一个n*n的矩阵， 然后从根节点和根节点 的两个子节点分别计算出距离然后， 如果根节点的距离和比左右的都小，之间返回答案， 然后分别计算左右两个节点的和， 朝小的分支递归下去， 时间复杂度为n*log(n)

对于第五题， 我的想法是， 对于一棵树， 任意两个点有唯一的路径， 那么对树进行一次遍历可以得到任意两个点之间的距离， 这样就得到了一个n*n的矩阵， 然后从根节点和根节点 的两个子节点分别计算出距离然后， 如果根节点的距离和比左右的都小，直接返回答案， 否者分别计算左右两个节点的和， 朝小的分支递归下去， 时间复杂度为n*log(n)。
我这里写的是二叉树， 实际适用于n叉树，

第二题 LC809
第五题 LC310

求到其他所有点平均距离最小的点? 和LC310好像不一样。。

第五题什么叫平均距离最小？ 树严格来说是有向的么不是？不能从child 到parentroot；那这个无向图是什么意思？

补充内容 (2018-5-4 16:55):

啊！忽视我，眼瞎看错。这个应该是310 了