Pythagorean distance nodes in a tree

Tree Breadth-First Search

57.7% acceptance

Mar 16, 2026

Given a tree, three distinct target nodes x, y, z. For each node u, compute distances dx, dy, dz to x, y, z. Count nodes where sorted (dx,dy,dz) form a Pythagorean triplet.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn special_nodes(n: i32, edges: Vec<Vec<i32>>, x: i32, y: i32, z: i32) -> i32 {
    let n = n as usize;
    let mut adj = vec![vec![]; n];
    for e in &edges {
      let u = e[0] as usize;
      let v = e[1] as usize;
      adj[u].push(v);
      adj[v].push(u);
    }

    fn bfs(start: usize, adj: &[Vec<usize>]) -> Vec<i64> {
      let n = adj.len();
      let mut dist = vec![-1i64; n];
      dist[start] = 0;
      let mut queue = std::collections::VecDeque::new();
      queue.push_back(start);
      while let Some(u) = queue.pop_front() {
        for &v in &adj[u] {
          if dist[v] == -1 {
            dist[v] = dist[u] + 1;
            queue.push_back(v);
          }
        }
      }
      dist
    }

    let dx = bfs(x as usize, &adj);
    let dy = bfs(y as usize, &adj);
    let dz = bfs(z as usize, &adj);

    let mut count = 0;
    for u in 0..n {
      let mut d = [dx[u], dy[u], dz[u]];
      d.sort_unstable();
      if d[0] * d[0] + d[1] * d[1] == d[2] * d[2] {
        count += 1;
      }
    }
    count
  }
}