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

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

问题是你只访问了你范围内的子节点。这意味着如果 node2 的值为 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。

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

Sum of all children nodes values in a specific range

java

binary-tree

treenode

arraylist