1

考虑以下二叉树：（取自此处）

鉴于叶节点要么是真要么是假，我怎样才能找到所有叶节点都为真的分支（或多个分支）？

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

即使为这种类型的搜索识别这个名称也会有所帮助，所以我可以谷歌它。

4

2 回答 2

2

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

这是一些 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 and y, if的第二个参数x已经为假。然而，在这种情况下，如果左分支不是全真，这将导致不访问右分支，从而错过一些全真分支。因此，递归调用最好转到单独的行。

于 2013-02-05T14:07:18.170 回答
0

如果两个孩子的子树的所有叶子都为真，则您可以进行后序树遍历并标记每个非叶节点 x 为真，否则为假（这是孩子标签的 AND 操作）。这样你就可以用你想要的属性递归地标记整棵树。

于 2013-02-05T14:08:07.510 回答