algorithm - 找到所有叶子节点都为真的分支

Question

考虑以下二叉树:(取自 here )

鉴于叶节点要么为真要么为假，我如何找到所有叶节点都为真的分支(或多个分支)？

因此，如果只有 8、5、6 或 7 为真，则第一个分支不会匹配(需要 9 为真才能匹配)，但第二个分支会匹配，因为它的所有叶子都为真。

即使为此类搜索识别此名称也会有所帮助，以便我可以通过 Google 搜索。

Answer 1

您可以使用递归函数，更深入地研究树并自下而上确定某个分支的所有叶子是否都为真。然后可以将这些分支存储在某个列表中。

这是一些 Python 代码。以树的根节点作为第一个参数和一个空列表作为第二个参数调用此函数，列表将填充正确的分支。

def allTrue(node, trueList=[]):
    if isLeaf(node):
        return node.value == True
    else:
        leftTrue = allTrue(node.left, trueList)
        rightTrue = allTrue(node.right, trueList)
        bothTrue = leftTrue and rightTrue
        if bothTrue:
            trueList.append(node)
        return bothTrue

需要注意的一件事:如果 x 为 false，许多编程语言通过不评估 x 和 y 的第二个参数来尝试变得聪明或懒惰已经。然而，在这种情况下，如果左分支不是全真，这将导致不访问右分支，从而错过一些全真分支。因此，递归调用最好转到不同的行。