返回二进制树蟒节点的平均值递归

Question

假设我有一个二叉树这样：

我想创建一个返回树，在这种情况下是(5+3+2+6)/(4) = 4的平均值的函数。

我做我前序遍历，这里是我的功能：

def helper(root, total=0, amount=0): 
    if root != None: 
     total += root.data 
     amount += 1 
     helper(root.left, total, amount) 
     helper(root.right, total, amount)  

    return (root, total, amount) 

def avg(root): 
    av = helper(root) 
    return av[1]/av[2] 

但是这个代码仅返回(Node 5, total = 5, amount = 1)。这就像它只扫描first节点，我不知道为什么或以上的代码有什么问题。

class btn(object): 

    def __init__(self, data): 
     self.data = data 
     self.left = None 
     self.right = None 

Answer 1

反模式检测

。此页面上的其他答案已经被犯同样的错误

def avg (tree): 
    def helper (node, sum, count): 
    if node is None: 
     return (0, 0) 
    else: 
     (Lsum, Lcount) = helper(node.left, 0, 0) 
     (Rsum, Rcount) = helper(node.right, 0, 0) 
     return (node.data + Lsum + Rsum, 1 + Lcount + Rcount) 
    (sum, count) = helper(tree, 0, 0) 
    return sum/count if count > 0 else None 

# your node class 
class Node (object): 
    def __init__(self, data, left, right): 
    self.data = data 
    self.left = left 
    self.right = right 

# make your tree 
tree = Node(5, Node(3, Node(2, None, None), None), Node(6, None, None)) 

print(avg(tree)) #=> 4.0 

# ensure that this works for an empty tree too (it does) 
print(avg(None)) #=> None 

失败你

---

直觉

递归允许我们开发这个一个很好的直觉 - 特别是粗体线

(Lsum, Lcount) = helper(node.left, 0, 0) 
(Rsum, Rcount) = helper(node.right, 0, 0) 
return (node.data + Lsum + Rsum, 1 + Lcount + Rcount)

return这就是说retu RN的(sum, count)其中

• 一个元组为总和，这个节点的数据加上无论左右的款项是
• 为计数，算上这个节点（1），加上左不管，右计数是

通过编写这种方式，我们可以非常清楚的看到这两种情况我们的函数来处理：

1. 当一个节点为None，我们的贡献(0, 0)到最后计算
2. 否则，我们的贡献节点的data到总和，并1到计数。

---

内嵌代码解释

# we only need to expose one function 
def avg (tree): 

    # helper isn't exposed outside of avg 
    # helper has stateful parameters 
    def helper (node, sum, count): 

    # helper is a recursive function, start with the base case of empty Node 
    if node is None: 
     # our base sum and count are 0 
     return (0, 0) 

    # process the Node 
    else: 

     # get L sum and count the same way we initialized helper with the tree 
     (Lsum, Lcount) = helper(node.left, 0, 0) 

     # do the same for the R side 
     (Rsum, Rcount) = helper(node.right, 0, 0) 

     # no reassignment of sum or count is necessary, 
     # simply recurse using the new state values of each 
     return (
     node.data + Lsum + Rsum, # sum equals this node plus L and R sums 
     1 + Lcount + Rcount  # count equals 1 plus L and R counts 
    ) 

    # always init the sum and count with 0 
    (sum, count) = helper(tree, 0, 0) 

    # don't divide by zero if the tree is empty; instead return None 
    return sum/count if count > 0 else None 

---

清理所有的中间值

让我们一起来看看这款

(Lsum, Lcount) = helper(node.left, 0, 0) 
(Rsum, Rcount) = helper(node.right, 0, 0) 
return (node.data + Lsum + Rsum, 1 + Lcount + Rcount) 

如果您和我一样，尽管事实上这是对使用重新分配的其他答案的巨大改进，但它仍然使用中间值。如果我们可以稍微清理一下，我们会很高兴的。

如果我们有一个函数可以获取元组列表并将所有值添加到它们各自的位置，该怎么办？

// if only ... 
sum_tuples((0, 10), (1, 20), (2, 30)) 
# ... (0 + 1 + 2 , 10 + 20 + 30) 
#=> (3, 60) 

原来，功能其实是很容易与zip帮助写。此功能是操作通用的，所以它是比我们avg功能等地有用的，所以我就单独把它定义

def sum_tuples (*xs): 
    return tuple(sum(x) for x in zip(*xs)) 

sum_tuples((0,10), (1,20), (2,30)) 
#=> (3, 60) 

现在看它有avg的影响 - 在没有更多的中间值（变化大胆）

def avg (tree): 
    def helper (node, sum, count): 
    if node is None: 
     return (0, 0) 
    else: 
     return sum_tuples( (node.data, 1), 
     helper(node.left, 0, 0), 
     helper(node.right, 0, 0) 
     ) 
    (sum, count) = helper(tree, 0, 0) 
    return sum/count if count > 0 else None

当然，它的工作原理和以前一样，只是现在它只是一样美丽即可。

Answer 2

致电helper时，您没有使用返回值。这些应被用来确定在整个树值的总和：

def helper(root, total=0, amount=0): 
    if root != None: 
     total += root.data 
     amount += 1 
     _, left_total, left_amount = helper(root.left, total, amount) 
     _, right_total, right_amount = helper(root.right, total, amount) 
     total += left_total 
     total += right_total 
     amount += left_amount 
     amount += right_amount 

    return (root, total, amount) 

下面的行“解包”从helper的返回值到每个三个值之一：

_, left_total, left_amount = helper(root.left, total, amount) 

第一的这三个值被分配到_，但被忽略了（变量_通常用在这种情况下），然后有left_total和left_amount这是返回的元组中的第二个和第三个值。

Answer 3

def helper(root, total=0, amount=0): 
if root != None: 
    total += root.data 
    amount += 1 
    (_, total, amount) = helper(root.left, total, amount) 
    (_, total, amount) = helper(root.right, total, amount) 
return (root, total, amount) 

你给目前的总金额，并在辅助功能，但你不存储它们返回的新值。有没有必要使用重新分配，以增加更多的复杂性 - 你已经在使用递归与状态变量