python - 如何使用ADT在python中搜索二叉树节点以获得最长的树

Question

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):

但我只是不知道从那里去哪里。你能帮我解决这个问题吗？

Answer 1

我会编写一个函数来迭代树中所有可能的路径。然后我会迭代这些路径，选择加起来是七的倍数的路径，然后从其中选择最长的路径。

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]]