We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.
n
0
n - 1
You are given the integer n and the array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
edges
edges[i] = [ai, bi]
ai
bi
Return an array answer of length n where answer[i] is the sum of the distances between the ith node in the tree and all other nodes.
answer
answer[i]
ith
The text was updated successfully, but these errors were encountered:
using System; using System.Collections.Generic; public class Solution { public int[] SumOfDistancesInTree(int n, int[][] edges) { int[] ans = new int[n]; int[] count = new int[n]; HashSet<int>[] tree = new HashSet<int>[n]; for (int i = 0; i < n; ++i) { tree[i] = new HashSet<int>(); count[i] = 1; } foreach (int[] edge in edges) { int u = edge[0]; int v = edge[1]; tree[u].Add(v); tree[v].Add(u); } Postorder(tree, 0, -1, count, ans); Preorder(tree, 0, -1, count, ans); return ans; } private void Postorder(HashSet<int>[] tree, int node, int parent, int[] count, int[] ans) { foreach (int child in tree[node]) { if (child == parent) continue; Postorder(tree, child, node, count, ans); count[node] += count[child]; ans[node] += ans[child] + count[child]; } } private void Preorder(HashSet<int>[] tree, int node, int parent, int[] count, int[] ans) { foreach (int child in tree[node]) { if (child == parent) continue; ans[child] = ans[node] - count[child] + (tree.Length - count[child]); Preorder(tree, child, node, count, ans); } } }
Sorry, something went wrong.
F4NT0
No branches or pull requests
There is an undirected connected tree with
n
nodes labeled from0
ton - 1
andn - 1
edges.You are given the integer
n
and the arrayedges
whereedges[i] = [ai, bi]
indicates that there is an edge between nodesai
andbi
in the tree.Return an array
answer
of lengthn
whereanswer[i]
is the sum of the distances between theith
node in the tree and all other nodes.Example 1
Example 2
Example 3
Constraints:
The text was updated successfully, but these errors were encountered: