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

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. 1. 已知总共有n个节点（编号 0~n-1），创建一个长度为n的列表，列表中每个位置对应一个节点，存储该节点直接相连的所有邻居节点。

2. 2. 遍历输入的所有边（共 n-1 条），每一条边连接两个节点v和w：

• • 把w添加到v的邻居列表中；

• • 把v添加到w的邻居列表中（因为是无向树，边是双向的）。

3. 最终得到完整的树的邻接表，后续所有距离计算都基于这个结构进行。

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

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

1. 1. 创建一个长度为n的距离数组，初始值全为 0（数组下标对应节点编号，值对应距离）。

2. 2. 从起点开始做深度优先遍历（DFS），遍历规则：

• • 记录当前遍历到的节点，以及它的「父节点」（避免走回头路）；

• • 遍历当前节点的所有邻居，跳过父节点（防止重复遍历）；

• • 邻居节点的距离 = 当前节点距离 + 1；

• • 递归遍历这个邻居节点，重复上述操作。

3. 遍历完成后，距离数组中就存储了起点到树上每一个节点的距离。

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

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

1. 1. 以x为起点，计算得到数组dx：dx[i]表示节点i到x的距离；

2. 2. 以y为起点，计算得到数组dy：dy[i]表示节点i到y的距离；

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

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

1. 1. 取出节点i的三个距离：dx[i]、dy[i]、dz[i]；

2. 2. 对这三个数字从小到大排序，得到排序后的三个数a、b、c（a ≤ b ≤ c）；

3. 3. 验证勾股定理：判断a² + b²是否等于c²；

4. 4. 如果满足等式，该节点就是特殊节点，计数加 1；不满足则跳过。

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

时间复杂度分析

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

1. 1.构建邻接表：遍历 n-1 条边，复杂度为O(n)；

2. 2.三次距离计算：每次DFS遍历整棵树，所有节点和边都访问一次，单次 O(n)，三次总复杂度O(3n) = O(n)；

3. 3.节点判断与计数：遍历 n 个节点，每个节点仅做排序（3个数字排序是常数时间 O(1)）和简单计算，总复杂度O(n)。

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

空间复杂度分析

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

1. 1.邻接表：存储 n 个节点和 n-1 条边，空间O(n)；

2. 2.距离数组：一共创建 3 个长度为 n 的数组，空间O(3n) = O(n)；

3. 3.DFS递归栈：树的深度最坏为 n（链状树），递归栈空间O(n)；

4. 4. 其他变量（计数、临时数组）均为常数空间 O(1)。

总空间复杂度：O(n)

总结

1. 1. 核心流程：建邻接表 → 三次DFS算距离 → 遍历节点验证勾股定理 → 统计结果；

2. 2. 时间复杂度：O(n)（线性时间，高效处理十万级节点）；

3. 3. 空间复杂度：O(n)（线性空间，符合题目内存要求）。

package main

 import (
    "fmt"
    "slices"
)

 func specialNodes(n int, edges [][]int, x, y, z int) (ans int) {
    g := make([][]int, n)
    for _, e := range edges {
        v, w := e[0], e[1]
        g[v] = append(g[v], w)
        g[w] = append(g[w], v)
    }

     calcDis := func(start int) []int {
        dis := make([]int, n)
        var dfs func(int, int)
        dfs = func(v, fa int) {
            for _, w := range g[v] {
                if w != fa {
                    dis[w] = dis[v] + 1
                    dfs(w, v)
                }
            }
        }
        dfs(start, -1)
        return dis
    }

     dx := calcDis(x)
    dy := calcDis(y)
    dz := calcDis(z)

     for i := range n {
        a := []int{dx[i], dy[i], dz[i]}
        slices.Sort(a)
        if a[0]*a[0]+a[1]*a[1] == a[2]*a[2] {
            ans++
        }
    }
    return
}

 func main() {
    n := 4
    edges := [][]int{{0, 1}, {0, 2}, {0, 3}}
    x := 1
    y := 2
    z := 3
    result := specialNodes(n, edges, x, y, z)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 from typing import List

 def specialNodes(n: int, edges: List[List[int]], x: int, y: int, z: int) -> int:
    # 构建邻接表
    g = [[] for _ in range(n)]
    for v, w in edges:
        g[v].append(w)
        g[w].append(v)

     # 计算从 start 出发到所有节点的距离
    def calcDis(start: int) -> List[int]:
        dis = [0] * n
        visited = [False] * n
        def dfs(v: int):
            visited[v] = True
            for w in g[v]:
                if not visited[w]:
                    dis[w] = dis[v] + 1
                    dfs(w)
        dfs(start)
        return dis

     dx = calcDis(x)
    dy = calcDis(y)
    dz = calcDis(z)

     ans = 0
    for i in range(n):
        a = [dx[i], dy[i], dz[i]]
        a.sort()
        if a[0] * a[0] + a[1] * a[1] == a[2] * a[2]:
            ans += 1
    return ans

 def main():
    n = 4
    edges = [[0, 1], [0, 2], [0, 3]]
    x = 1
    y = 2
    z = 3
    result = specialNodes(n, edges, x, y, z)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

   


 using namespace std;

 int specialNodes(int n, vector 
 
 int 
 >>& edges,  
 int 
  x,  
 int 
  y,  
 int 
  z) { 
 
 
      
 // 构建邻接表 
 
 
     vector 
 
 int 
 >> g(n); 
 
 
      
 for 
  (auto& e : edges) { 
 
 
          
 int 
  v = e[ 
 0 
 ], w = e[ 
 1 
 ]; 
 
 
         g[v].push_back(w); 
 
 
         g[w].push_back(v); 
 
 
     } 
 
 
 
 
      
 // 计算从 start 出发到所有节点的距离 
 
 
     auto calcDis = [&]( 
 int 
  start) -> vector< 
 int 
 > { 
 
 
         vector< 
 int 
 > dis(n,  
 0 
 ); 
 
 
 
 
          
 // DFS 函数声明 
 
 
         function 
 
 int 
 ,  
 int 
 )> dfs = [&]( 
 int 
  v,  
 int 
  fa) { 
 
 
              
 for 
  ( 
 int 
  w : g[v]) { 
 
 
                  
 if 
  (w != fa) { 
 
 
                     dis[w] = dis[v] +  
 1 
 ; 
 
 
                     dfs(w, v); 
 
 
                 } 
 
 
             } 
 
 
         }; 
 
 
 
 
         dfs(start,  
 -1 
 ); 
 
 
          
 return 
  dis; 
 
 
     }; 
 
 
 
 
     vector< 
 int 
 > dx = calcDis(x); 
 
 
     vector< 
 int 
 > dy = calcDis(y); 
 
 
     vector< 
 int 
 > dz = calcDis(z); 
 
 
 
 
      
 int 
  ans =  
 0 
 ; 
 
 
      
 for 
  ( 
 int 
  i =  
 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++; 
 
 
         } 
 
 
     } 
 
 
 
 
      
 return 
  ans; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
      
 int 
  n =  
 4 
 ; 
 
 
     vector 
 
 int 
 >> edges = {{ 
 0 
 ,  
 1 
 }, { 
 0 
 ,  
 2 
 }, { 
 0 
 ,  
 3 
 }}; 
 
 
      
 int 
  x =  
 1 
 , y =  
 2 
 , z =  
 3 
 ; 
 
 
 
 
      
 int 
  result = specialNodes(n, edges, x, y, z); 
 
 
     cout << result << endl; 
 
 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。