java - Java 中的二叉树和递归

Question

我有一个节点类如下:

public class Node {

    private int value;
    private Node leftNode;
    private Node rightNode;

    public Node(Node leftNode, Node rightNode, int value){
        this.leftNode = leftNode;
        this.rightNode = rightNode;
        this.value = value;
    }

   //Getter and Setter methods for these variables are defined here
}

此 Node 类用于创建二叉树。我正在用 JAVA 编写一个递归函数来计算所有节点的平均值。我在下面写的代码没有给出正确的答案。我认为这是因为传递了参数 average 和 nodeCount 的值，而不是引用。

public double treeAverage(Node node, double average, int nodeCount){

    nodeCount ++;
    if(node == null) return Double.MAX_VALUE;
    if(node.getLeftNode()==null && node.getRightNode()==null){
        average = ( average + node.getValue() )/nodeCount;
    }

    if(node.getLeftNode()!=null){
        average = treeAverage(node.getLeftNode(), average, nodeCount); 
    }
    if(node.getRightNode()!=null){
        average = treeAverage(node.getRightNode(), average, nodeCount);
    }

    return average;

}

在 Java 中纠正这个递归函数的正确方法是什么？ (在 C 中，我可以传递对这些参数的引用)。如果我错了，请纠正我。

Answer 1

我猜你可以使用辅助方法。类似这样的东西(我没有编译这段代码，应该被当作提示)

private static long count = 0L;
private static long sum = 0L;


public static int treeAverageHelper(Node node){

    if(node == null) return 0;
    count ++;
    return node.val + treeAverageHelper(node.left) + treeAverageHelper(node.right);
}

public static double treeAvg(Node n){
    sum = treeAverageHelper(n);
    if (count == 0)
        return 0D;
    else
        return (double)sum/count;
}

助手，遍历树聚合和计数。最后将两者分开。