树：预序横向

Question

import java.util.*;

class Node {
    String id;
    int point;
    List<Node> children;
    Node parent;

    Node(String id) {
        this.id = id;
        this.point = 0;
        this.children = new ArrayList<>();
        this.parent = null;
    }
}

class Solution {
    private static Map<String, Node> nodeMap = new HashMap<>();

    public static Node buildTree(String rootId, List<String[]> queries) {
        Node root = new Node(rootId);
        nodeMap.put(rootId, root);
        
        for (String[] query : queries) {
            String recruiterId = query[0];
            String recruitId = query[1];
            
            Node recruiterNode = nodeMap.getOrDefault(recruiterId, new Node(recruiterId));
            Node recruitNode = nodeMap.getOrDefault(recruitId, new Node(recruitId));
            
            recruiterNode.children.add(recruitNode);
            recruitNode.parent = recruiterNode;
            
            updateAncestors(recruiterNode, 1);
            
            nodeMap.put(recruiterId, recruiterNode);
            nodeMap.put(recruitId, recruitNode);
        }
        
        return root;
    }

    private static void updateAncestors(Node node, int point) {
        while (node != null) {
            if (node.parent != null && !node.parent.children.isEmpty()) {
                boolean hasGrandChildren = false;
                boolean hasChildren = false;
                
                for (Node child : node.children) {
                    if (hasGrandChildren(child)) {
                        hasGrandChildren = true;
                        break;
                    }
                }
                
                if (!node.children.isEmpty()) {
                    hasChildren = true;
                }
                
                if (hasGrandChildren) {
                    node.point += 3;
                } else if (hasChildren) {
                    node.point += 2;
                } else {
                    node.point += 1;
                }
            } else {
                node.point += 1;
            }
            node = node.parent;
        }
    }

    private static boolean hasGrandChildren(Node node) {
        if (node.children.isEmpty()) {
            return false;
        }
        
        for (Node child : node.children) {
            if (!child.children.isEmpty()) {
                return true;
            }
            if (hasGrandChildren(child)) {
                return true;
            }
        }
        
        return false;
    }

    public static void preorderTraversal(Node root) {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            Node current = stack.pop();
            System.out.println(current.id + " " + current.point);
            
            for (int i = current.children.size() - 1; i >= 0; i--) {
                stack.push(current.children.get(i));
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String yourId = scanner.nextLine();
        int T = Integer.parseInt(scanner.nextLine());
        List<String[]> queries = new ArrayList<>();
        
        for (int i = 0; i < T; i++) {
            String[] query = scanner.nextLine().split(" ");
            queries.add(query);
        }
        
        Node root = buildTree(yourId, queries);
        preorderTraversal(root);
    }
}

如果孩子有孩子，如何确保父母或祖先获得 1 分奖励？
示例：
输入

011 (root)
10 (amount of data)
011 012
011 013
011 014
014 023
014 022
014 033
011 015
015 077
015 088
088 039

输出

011 14
012 0
013 0
014 6
023 0
022 0
033 0
015 5
077 0
088 2
039 0

如果父节点有子节点，则每个子节点将获得 2 分，如果子节点有子节点，则父节点/祖先节点将获得 1 个奖励分。 （获得1分奖励/孙子）
#节点 011 有 14 分，因为它有子节点：节点 012、013、014 和 015。但是节点 014（3 个子节点）、015（2 个子节点）也有子节点，节点 088 有子节点，因此节点 011 获得 1 个奖励分/孙子（2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1）。
这是我的输出](https://i.sstatic.net/gw2qp2nI.png)

Answer 1

您所解释的收集积分规则可归结为以下逻辑：

节点为其拥有的每个后代获得一个点，并为它拥有的每个子节点获得一个点。由于子节点既是后代又是子节点，因此子节点将通过这种方式贡献 2 分。

在

updateAncestors

中你把事情变得过于复杂了。它变得如此复杂的原因是这个函数是在树尚未完全构建时调用的。

我建议首先构建整个树，然后您可以应用一个简单的逻辑：对于每个节点执行以下操作：

• 将其拥有的孩子数量添加到其积分中
• 向上遍历树，给到根的路径上的每个节点加1。

就是这样。

以下是您的

buildTree

可以解决的问题：

    public static Node buildTree(String rootId, List<String[]> queries) {
        Node root = new Node(rootId);
        nodeMap.put(rootId, root);

        for (String[] query : queries) {
            String recruiterId = query[0];
            String recruitId = query[1];

            Node recruiterNode = nodeMap.getOrDefault(recruiterId, new Node(recruiterId));
            Node recruitNode = nodeMap.getOrDefault(recruitId, new Node(recruitId));

            recruiterNode.children.add(recruitNode);
            recruitNode.parent = recruiterNode;

            // Don't calculate points yet. First finish building the tree.

            nodeMap.put(recruiterId, recruiterNode);
            nodeMap.put(recruitId, recruitNode);
        }
        // Now distribute the points:
        for (Node recruiterNode : nodeMap.values()) {
            // 1 point per direct child
            recruiterNode.point += recruiterNode.children.size(); 
            // Grant a bonus point to every ancestor:
            Node ancestor = recruiterNode.parent;
            while (ancestor != null) {
                // 1 point as this is an ancestor of recruiterNode
                ancestor.point += 1; 
                ancestor = ancestor.parent;
            }
        }
        return root;
    }