确定树结构中所有节点值的平均值

Question

鉴于此界面...

public static interface Node 
{
    int getValue();
    List<Node> getChildren();
}

执行以下方法return树中所有节点值的平均值。

public static double getAverage(Node root) 
{
}

我很难解决这个练习题，有几个问题。

我假设最好使用递归来完成，对吗？
如果没有辅助方法或全局变量，这可能吗？
这是否可以不必遍历树两次？（一次用于节点总和，一次用于节点计数）

此外，如果有人可以提供一些伪代码，我将不胜感激。

Answer 1

你可以使用递归，但没有它也可以解决这个问题。您需要的只是深度优先搜索。您可以使用堆栈迭代实现它。
是的，这是可能的。带有堆栈的版本不需要任何额外的方法。
是的，这是可能的。您可以在一次遍历期间只计算这两个值。

下面是一个非递归实现的伪代码：

valuesSum = 0
nodesCount = 0
stack = new Stack
stack.add(root)
while (!stack.isEmpty())
    Node v = stack.poll()
    nodesCount++
    valuesSum += v.getValue()
    for (child : v.getChildren())
        stack.add(child)
return valuesSum / nodesCount

确定树结构中所有节点值的平均值

Determine average of all Node values within a Tree Structure

java

tree

recursion