我必须为二叉树中的每一级实现一个求和 我必须返回一个列表,该列表在位置I处包含第I个和 如果我有这棵树
24
/ \
14 27
/ \ / \
11 20 12 55
我必须返回[24,41,98]
我试图用python实现这个解决方案
def sommaperlivelli(p, lista):
if p == None:
return
if p.left != None and p.right != None:
lista.append(p.left.key + p.right.key)
sommaperlivelli(p.left, lista)
sommaperlivelli(p.right, lista)
return lista
我只能得到第一个和,不能加根。我怎么能做到
这是我使用的类
class NodoABR:
def __init__(self, key = None, left = None, right = None, parent = None):
self.key = key
self.left = left
self.right = right
self.parent = parent
这就是我如何将节点添加到树中的方法
def inserisciNodo(p, n):
if p == None:
return NodoABR(n)
else:
if p.key == n:
return p
elif p.key < n:
rchild = inserisciNodo(p.right, n)
p.right = rchild
rchild.parent = p
else:
lchild = inserisciNodo(p.left, n)
p.left = lchild
lchild.parent = p
return p
这是一个二进制搜索树 在主要功能中,我这样做
p = NodoABR(24)
p = inserisciNodo(p, 14)
p = inserisciNodo(p, 27)
p = inserisciNodo(p, 11)
p = inserisciNodo(p, 20)
p = inserisciNodo(p, 12)
p = inserisciNodo(p, 55)
print(sommaperlivelli(p,[]))
假设您有类似的树节点类,您可以试试这个&;修改以满足您的特殊需要
例如:
[编辑]PO作者想学习另一种方法。(非排队)
使用您的
NodoABR
类,这里有一个简单的树遍历,深度优先,我们注意到每个迭代的级别,并使用它存储节点值,arr
是一个列表数组(或列表),每个级别一个:这是输出:
相关问题 更多 >
编程相关推荐