基于Java树前序遍历代码，如何实现父/祖先节点获孙节点1分奖励？

需求规则 #

• 父节点每拥有一个子节点，获得2积分；
• 若某个节点存在后代节点（子节点的子节点及更底层节点），则该节点及其所有祖先节点，每拥有一个这样的后代节点，额外获得1积分。（等价于：每新增一个节点，其父节点加2分，所有祖父及以上祖先各加1分）

示例输入 #

011
10
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

现有错误代码 #

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);
    }
}

问题分析与修改方案 #

原代码的updateAncestors方法逻辑完全偏离需求，错误地通过判断节点是否有孙节点来累加分数，没有按照规则实现积分计算。

正确的逻辑是：

1. 每新增一个子节点，其父节点直接获得2分；
2. 该子节点的所有祖父及以上祖先节点，每个获得1分（因为这个新节点是他们的孙节点或更底层后代）。

修改后的代码 #

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;
            
            // 父节点加2分
            recruiterNode.point += 2;
            // 所有祖父及以上祖先各加1分
            Node ancestor = recruiterNode.parent;
            while (ancestor != null) {
                ancestor.point += 1;
                ancestor = ancestor.parent;
            }
            
            nodeMap.put(recruiterId, recruiterNode);
            nodeMap.put(recruitId, recruitNode);
        }
        
        return root;
    }

    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. 删除了原有的updateAncestors和hasGrandChildren方法，简化逻辑；
2. 在添加子节点的循环中，直接给父节点加2分；
3. 从父节点的父节点开始，向上遍历所有祖先节点，每个节点加1分；
4. 逻辑完全贴合需求，计算结果与示例输出一致。

内容的提问来源于stack exchange，提问作者Rob