特定范围内所有子节点值的总和

Question

我试图将其根节点的特定范围内的节点的所有子值相加。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Program {
    public static class Node {
        int data;
        List<Node> children;

        public Node(int data) {
            this.data = data;
            children = new ArrayList<>();
        }
        
        public void addChildren(Node... children) {
            this.children.addAll(Arrays.asList(children));
        }
        
    }
    
    public int sumRange(Node root, int min, int max) {
        int sum = 0;
        
        if(root.data >= min && root.data <= max) {
            sum = root.value;
        }
        
        int size = root.children.size();
        
        for (int i = 0; i < size; ++i) {
            if(root.children.get(i).data >= min && root.children.get(i).data <= max) {
                sum += sumRange(root.children.get(i), min, max);
            }
        }
        
        return sum;
    }
    
    public static void main(String[] args) {
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        
        
        Node node2 = new Node(2);
        node2.addChildren(node3, node4);
        Node node5 = new Node(5);
        node5.addChildren(node6, node7);
        Node node8 = new Node(8);
        
        Node node1 = new Node(1);
        node1.addChildren(node2, node5, node8);
        Program program = new Program();
        
        System.out.println(program.sumRange(node1, 3, 5)); // Should print 12
        
        System.out.println(program.sumRange(node2, 3, 5)); // Should print 7
        
    }
    
}

我尝试使用这段代码来计算特定范围之间的节点总和：

public int sumRange(Node root, int min, int max) {
    int sum = 0;

    if(root.data >= min && root.data <= max) {
        sum = root.value;
    }

    int size = root.children.size();

    for (int i = 0; i < size; ++i) {
        if(root.children.get(i).data >= min && root.children.get(i).data <= max) {
            sum += sumRange(root.children.get(i), min, max);
        }
    }

    return sum;
}

并且，它的总和正确地只有没有子节点的节点。在这一行中，node1 有多个子节点，它应该只计算特定范围节点，其总和结果应为 12。但它打印总和结果 5。

System.out.println(program.sumRange(node1, 3, 5)); // Should print 12

我也想计算所有子节点数据。任何帮助将不胜感激！

Answer 1

问题是您只访问您范围内的子节点。这意味着如果节点 2 的值为 2，则其子节点永远不会被访问，并且您无法将值 3 和 4 相加。问题的解决方案是删除循环中的 if 条件，如下所示：

    public int sumRange(Node root, int min, int max) {
        int sum = 0;

        if(root.data >= min && root.data <= max) {
            sum = root.data;
        }

        int size = root.children.size();
        for (int i = 0; i < size; ++i) {
                sum += sumRange(root.children.get(i), min, max);
        }
        
        return sum;
    }

如果再次尝试，节点 1 的输出应为 12 。