leetcode834.树中距离之和---我把你当兄弟，你却认我做爸爸

题目：
https://leetcode-cn.com/problems/sum-of-distances-in-tree/
这道题虽然我的答案和最快的答案时间差距还是有的，但是加入node之后，更容易理解了
简述这道题就是，本来我和你是朋友，慢慢的，你居然想让我当你儿子

public int[] sumOfDistancesInTree(int N, int[][] edges) {
    if (N == 1) {
        return new int[]{0};
    }
    TNode[] nodes = new TNode[N];
    int[] ans = new int[N];
    for (int i = 0; i < edges.length; i++) {
        TNode node = nodes[edges[i][0]];
        TNode nodeC = nodes[edges[i][1]];
        if (nodeC == null) {
            nodeC = new TNode(edges[i][1]);
            nodes[edges[i][1]] = nodeC;
        }
        if (node == null) {
            node = new TNode(edges[i][0]);
            nodes[edges[i][0]] = node;
        }
        //因为是无向图，所以大家互为朋友
        node.friends.add(nodeC);
        nodeC.friends.add(node);
    }
    TNode top = nodes[0];//选择你当老大
    getNumAnsS(null, top);
    top.score = top.scoreC;//祖宗的得分知道了
    setScore(top, ans, N);
    return ans;
}

private void setScore(TNode node, int[] ans, int N) {
    ans[node.key] = node.score;
    for (TNode children : node.friends) {
        //自己到各个路径的和为：已知父亲的得分，自己子孙的路径是更近的(- children.num),从父亲那边过来的更远(+ (N - children.num))
        children.score = node.score + (N - children.num) - children.num;
        setScore(children, ans, N);
    }
}

private void getNumAnsS(TNode top, TNode node) {
    if (node.friends.size() == 1) {
        node.num = 1;
        node.scoreC = 0;
    }
    node.friends.remove(top);//node把top当朋友，top想当爸爸，只能top找node，node找不到top
    int num = 1;
    int scoreC = 0;
    for (TNode children : node.friends) {//名义是朋友，实际当你是儿子
        getNumAnsS(node, children);
        num += children.num;
        scoreC += children.num + children.scoreC;
    }
    node.num = num;//我的子孙数为每个儿子的子孙数加自己
    node.scoreC = scoreC;//自己的到每个子孙的路径和是：我先到每个儿子那，再从儿子那，加上儿子的子孙路径
}

class TNode {
    int key;//我的值
    int score;//我最终的得分
    int scoreC;//我到我所有的子孙的路径
    int num;//包括自己，我的子孙有多少
    Set<TNode> friends = new HashSet<>();

    public TNode(int key) {
        this.key = key;
    }
}

最后

以上就是喜悦口红为你收集整理的leetcode834.树中距离之和---我把你当兄弟，你却认我做爸爸的全部内容，希望文章能够帮你解决leetcode834.树中距离之和---我把你当兄弟，你却认我做爸爸所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。