2026-05-28：树上的勾股距离节点。用go语言，给定一棵包含 n 个节点的无向树（节点编号为 0 到 n-1），树的边用长度为 n-1 的数组 edges 表示：edges[i] = [ui,

2026-05-28：树上的勾股距离节点。用go语言，给定一棵包含 n 个节点的无向树（节点编号为 0 到 n-1），树的边用长度为 n-1 的数组 edges 表示：edges[i] = [ui, vi] 表示 ui 与 vi 之间有一条无向边。再给定三个两两不同的目标节点 x、y、z。

对树中任意一个节点 u，分别计算它到 x、y、z 的距离，记为 dx、dy、dz。若将这三个距离中的数按从小到大排序后，得到的 (a, b, c) 满足 a² + b² = c²，则称该节点 u 为“特殊节点”。

要求统计树中所有特殊节点的个数，并返回该数量。

4 <= n <= 100000。

edges.length == n - 1。

edges[i] = [ui, vi]。

0 <= ui, vi, x, y, z <= n - 1。

x, y 和 z 互不相同。

输入生成的 edges 表示一棵有效的树。

输入： n = 4, edges = [[0,1],[0,2],[0,3]], x = 1, y = 2, z = 3。

输出： 3。

解释：

对于每个节点，我们计算它到节点 x = 1、y = 2 和 z = 3 的距离。

节点 0 的距离分别为 1, 1, 1。排序后，距离为 1, 1, 1，不满足勾股定理条件。

节点 1 的距离分别为 0, 2, 2。排序后，距离为 0, 2, 2。由于 02 + 22 = 22，节点 1 是特殊的。

节点 2 的距离分别为 2, 0, 2。排序后，距离为 0, 2, 2。由于 02 + 22 = 22，节点 2 是特殊的。

节点 3 的距离分别为 2, 2, 0。排序后，距离为 0, 2, 2。这也满足勾股定理条件。

因此，节点 1、2 和 3 是特殊节点，答案为 3。

题目来自力扣3820。

树上勾股距离节点解题步骤详解

第一步：构建无向树的邻接表存储结构

树是由节点和边组成的无向连通无环图，首先需要把输入的边信息转换成计算机容易遍历的存储结构——邻接表。

1. 已知总共有n个节点（编号 0~n-1），创建一个长度为n的列表，列表中每个位置对应一个节点，存储该节点直接相连的所有邻居节点。
2. 遍历输入的所有边（共 n-1 条），每一条边连接两个节点v和w：
   • 把w添加到v的邻居列表中；
   • 把v添加到w的邻居列表中（因为是无向树，边是双向的）。
3. 最终得到完整的树的邻接表，后续所有距离计算都基于这个结构进行。

第二步：实现「单源最短距离计算」功能

树的特性：任意两个节点之间有且仅有一条唯一路径，因此从一个起点到所有其他节点的距离，就是路径上的边数，用深度优先遍历（DFS）就能一次性算出所有距离。
这个功能的核心作用是：输入一个起点节点，输出该起点到树上所有节点的距离数组。
具体执行步骤：

1. 创建一个长度为n的距离数组，初始值全为 0（数组下标对应节点编号，值对应距离）。
2. 从起点开始做深度优先遍历（DFS），遍历规则：
   • 记录当前遍历到的节点，以及它的「父节点」（避免走回头路）；
   • 遍历当前节点的所有邻居，跳过父节点（防止重复遍历）；
   • 邻居节点的距离 = 当前节点距离 + 1；
   • 递归遍历这个邻居节点，重复上述操作。
3. 遍历完成后，距离数组中就存储了起点到树上每一个节点的距离。

第三步：分别计算三个目标节点到全节点的距离

题目给定了三个固定节点x、y、z，需要分别以这三个节点为起点，调用第二步的距离计算功能，得到三组距离数据：

1. 以x为起点，计算得到数组dx：dx[i]表示节点i到x的距离；
2. 以y为起点，计算得到数组dy：dy[i]表示节点i到y的距离；
3. 以z为起点，计算得到数组dz：dz[i]表示节点i到z的距离。
   至此，我们拿到了每个节点对应的三个距离值。

第四步：遍历所有节点，判断是否为「特殊节点」

逐个检查树上的每一个节点i（从 0 到 n-1），判断规则严格按照题目要求：

1. 取出节点i的三个距离：dx[i]、dy[i]、dz[i]；
2. 对这三个数字从小到大排序，得到排序后的三个数a、b、c（a ≤ b ≤ c）；
3. 验证勾股定理：判断a² + b²是否等于c²；
4. 如果满足等式，该节点就是特殊节点，计数加 1；不满足则跳过。

第五步：返回最终统计结果

遍历完所有节点后，统计得到的总数量，就是题目要求的答案。

时间复杂度分析

我们按照步骤拆分计算复杂度（n为节点总数）：

1. 构建邻接表：遍历 n-1 条边，复杂度为O(n)；
2. 三次距离计算：每次DFS遍历整棵树，所有节点和边都访问一次，单次 O(n)，三次总复杂度O(3n) = O(n)；
3. 节点判断与计数：遍历 n 个节点，每个节点仅做排序（3个数字排序是常数时间 O(1)）和简单计算，总复杂度O(n)。

总时间复杂度：O(n)
（线性复杂度，适合题目要求的 n ≤ 100000 大数据量）

空间复杂度分析

统计程序运行过程中占用的额外空间：

1. 邻接表：存储 n 个节点和 n-1 条边，空间O(n)；
2. 距离数组：一共创建 3 个长度为 n 的数组，空间O(3n) = O(n)；
3. DFS递归栈：树的深度最坏为 n（链状树），递归栈空间O(n)；
4. 其他变量（计数、临时数组）均为常数空间 O(1)。

总空间复杂度：O(n)

总结

1. 核心流程：建邻接表 → 三次DFS算距离 → 遍历节点验证勾股定理 → 统计结果；
2. 时间复杂度：O(n)（线性时间，高效处理十万级节点）；
3. 空间复杂度：O(n)（线性空间，符合题目内存要求）。

Go完整代码如下：

packagemainimport("fmt""slices")funcspecialNodes(nint,edges[][]int,x,y,zint)(ansint){g:=make([][]int,n)for_,e:=rangeedges{v,w:=e[0],e[1]g[v]=append(g[v],w)g[w]=append(g[w],v)}calcDis:=func(startint)[]int{dis:=make([]int,n)vardfsfunc(int,int)dfs=func(v,faint){for_,w:=rangeg[v]{ifw!=fa{dis[w]=dis[v]+1dfs(w,v)}}}dfs(start,-1)returndis}dx:=calcDis(x)dy:=calcDis(y)dz:=calcDis(z)fori:=rangen{a:=[]int{dx[i],dy[i],dz[i]}slices.Sort(a)ifa[0]*a[0]+a[1]*a[1]==a[2]*a[2]{ans++}}return}funcmain(){n:=4edges:=[][]int{{0,1},{0,2},{0,3}}x:=1y:=2z:=3result:=specialNodes(n,edges,x,y,z)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-fromtypingimportListdefspecialNodes(n:int,edges:List[List[int]],x:int,y:int,z:int)->int:# 构建邻接表g=[[]for_inrange(n)]forv,winedges:g[v].append(w)g[w].append(v)# 计算从 start 出发到所有节点的距离defcalcDis(start:int)->List[int]:dis=[0]*n visited=[False]*ndefdfs(v:int):visited[v]=Trueforwing[v]:ifnotvisited[w]:dis[w]=dis[v]+1dfs(w)dfs(start)returndis dx=calcDis(x)dy=calcDis(y)dz=calcDis(z)ans=0foriinrange(n):a=[dx[i],dy[i],dz[i]]a.sort()ifa[0]*a[0]+a[1]*a[1]==a[2]*a[2]:ans+=1returnansdefmain():n=4edges=[[0,1],[0,2],[0,3]]x=1y=2z=3result=specialNodes(n,edges,x,y,z)print(result)if__name__=="__main__":main()

C++完整代码如下：

#include<iostream>#include<vector>#include<algorithm>#include<functional>usingnamespacestd;intspecialNodes(intn,vector<vector<int>>&edges,intx,inty,intz){// 构建邻接表vector<vector<int>>g(n);for(auto&e:edges){intv=e[0],w=e[1];g[v].push_back(w);g[w].push_back(v);}// 计算从 start 出发到所有节点的距离autocalcDis=[&](intstart)->vector<int>{vector<int>dis(n,0);// DFS 函数声明function<void(int,int)>dfs=[&](intv,intfa){for(intw:g[v]){if(w!=fa){dis[w]=dis[v]+1;dfs(w,v);}}};dfs(start,-1);returndis;};vector<int>dx=calcDis(x);vector<int>dy=calcDis(y);vector<int>dz=calcDis(z);intans=0;for(inti=0;i<n;i++){vector<int>a={dx[i],dy[i],dz[i]};sort(a.begin(),a.end());if(a[0]*a[0]+a[1]*a[1]==a[2]*a[2]){ans++;}}returnans;}intmain(){intn=4;vector<vector<int>>edges={{0,1},{0,2},{0,3}};intx=1,y=2,z=3;intresult=specialNodes(n,edges,x,y,z);cout<<result<<endl;return0;}