T = [[[[], [3, []]], [5, [[[[], [6, []]], [2, [[], [1, []]]]], [4, [[], [3, [[], [7, []]]]]]]]], [2, [[], [8, []]]]]
是二叉树的表示。
上面的T
代码很长,滚动查看完整代码
我正在寻找最长的树,其节点总和是给定数字的倍数。
上面的 7
树 T
的示例为 searchMax(T, 7)
, [[2,5], [ 4,3], [7]]
返回,因为它是最长的,而且其总和是 7 的倍数
我定义了以下代码
def cons(x, y):
return [x, y]
def car(p):
return p[0]
def cdr(p):
return p[1]
nil = []
def makeBinTree(root, left, right):
return cons(left, cons(root, right))
emptyTree = nil
def isEmpty(tree):
if len(tree) < 1:
return True
else:
return False
def root(tree):
return tree[1][0]
def left(tree):
return tree[0][1]
def right(tree):
return [1][1]
def searchMax(tree, number):
但我只是不知道从那里去哪里。你能帮我解决这个问题吗?
最佳答案
我会编写一个函数来迭代树中所有可能的路径。然后我会迭代这些路径,选择加起来是七的倍数的路径,然后从其中选择最长的路径。
def isEmpty(tree):
if len(tree) < 1:
return True
else:
return False
def root(tree):
return tree[1][0]
def left(tree):
return tree[0]
def right(tree):
return tree[1][1]
def iter_all_paths(t):
if isEmpty(t):
return
yield [root(t)]
for child in (left(t), right(t)):
for path in iter_all_paths(child):
yield [root(t)] + path
def searchMax(t, x):
#find all paths that add up to a multiple of x
candidates = []
for path in iter_all_paths(t):
if sum(path) % x == 0:
candidates.append(path)
if not candidates:
return None
return max(candidates, key=len)
T = [[[[], [3, []]], [5, [[[[], [6, []]], [2, [[], [1, []]]]], [4, [[], [3, [[], [7, []]]]]]]]], [2, [[], [8, []]]]]
print(searchMax(T, 7))
结果:
[2, 5, 4, 2, 1]
这与您的预期结果 [2, 5, 4, 3, 7] 不同。这两个解决方案具有相同的长度,因此我认为返回其中之一就可以了。如果长度相同,我的解决方案将返回最左边的路径。
<小时/>也许你在想“其实我想要的不是最长的路径长度,而是最大的节点总和”。那么 [2, 5, 4, 3, 7] 将以七分优势击败 [2, 5, 4, 2, 1]。如果这就是您想要的,您可以将 searchMax
的最后一行更改为 return max(candidates, key=sum)
。
您可能还会想“我希望结果是列表的列表,而不是整数的列表。我希望每个子列表的总和等于数字的倍数。而不是 [2, 5, 4, 3, 7]
,我想要[[2, 5], [4, 3], [7]]
。
您可以编写一个函数,将列表排列成加起来等于数字的 block ,并在从 searchMax
返回之前调用该函数。
def chunk(seq, x):
result = [[]]
for item in seq:
result[-1].append(item)
if sum(result[-1]) % x == 0:
result.append([])
if not result[-1]:
del result[-1]
return result
#later, in searchMax...
return chunk(max(candidates, key=len), x)
结果:
[[2, 5], [4, 2, 1]]
关于python - 如何使用ADT在python中搜索二叉树节点以获得最长的树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53208547/