如何求树节点的最大距离？双BFS思路及InterviewBit代码解析

方法1：两次遍历法 #

这是最易理解的树直径求解思路，逻辑如下：

• 任选树中任意一个节点u
• 从u出发做一次DFS或BFS遍历全树，找到距离u最远的节点，记为x
• 再从x出发做一次DFS或BFS遍历全树，找到距离x最远的节点，记为q
• x到q的路径长度就是树的直径

思路正确性依据树的直径核心性质：树中任意节点的最远点，一定是直径的两个端点之一，所以两次找最远点就能定位直径的两个端点，两者的距离就是答案。

方法2：子树高度统计法（对应给出的代码逻辑） #

前提说明 #

给出的代码对应输入是父节点数组A，其中A[i]代表编号为i的节点的父节点编号，根节点的A值为-1，且所有子节点的编号都大于父节点编号，所以可以从后往前遍历节点，实现从叶子到根的处理顺序。

代码逐行解释 #

int Solution::solve(vector<int> &A)
{
   // 初始化hgt数组，hgt[i]代表以i为根的子树的最大高度（即i到子树叶子的最长边数），初始值都为0
   vector<int> hgt(A.size(),0);
   // ans存储全局最大距离，即最终的直径
   int ans=0,maxx=0;
   // 从最大的节点编号倒序遍历到1，根节点是0不需要遍历
   for(int i=A.size()-1;i>0;i--)
   {
       // 计算经过i的父节点的最长路径候选值：父节点当前已有的最大高度 + 当前节点子树高度 + 1（父节点到i的边）
       // 这个值就是父节点两个最长子树分支拼接起来的路径长度
       ans=max(ans,hgt[A[i]]+hgt[i]+1);
       // 更新父节点的最大高度：如果当前节点的子树高度+1比父节点之前的最大高度大，就替换
       hgt[A[i]]=max(hgt[i]+1,hgt[A[i]]);
   }
   return ans;
}

思路逻辑 #

这种方法本质是后序遍历的变种，遍历每个节点的时候，统计它的所有子树的最大高度和第二大高度，两者相加再加上两条边（根到两个子树的边）就是经过当前节点的最长路径，全局所有节点的最长路径的最大值就是树的直径。因为本题输入的子节点编号都大于父节点，所以倒序遍历就能保证处理父节点之前，所有子节点都已经处理完毕，不需要递归实现后序遍历，效率更高。

内容的提问来源于stack exchange，提问作者Shubham Sharma