给定一颗无根树,假设它有n个节点,节点编号从1到n,求任意两点之间的距离之和,要求时间复杂度为O(n)
任取一个根为起点进行dfs,记录每个结点到根的距离之和。dfs整棵树的复杂度是O(N).假设根节点编号为0,节点i与节点0的距离之和为len[i]那么询问节点i和j的距离之和,就是abs(len[i]-len[j])每次询问复杂度为O(1),总复杂度O(N)有不会的可以问我,希望采纳!