Python 中的深度优先搜索从不 returns True

Question

在明显包含 3 的树中搜索“3”时，代码将进入正确的 "if statement"，但不会 return 正确。这是为什么？

class Node:
    def __init__(self):
        self.value = None
        self.leftChild = None
        self.rightChild = None

def dfs(root, sought):

    print "root", root.value
    print "sought", sought.value

    if root.value == sought.value:
        print "inside root = sought"
        return True

    elif root.leftChild is not None and root.rightChild is not None:
        dfs(root.leftChild, sought)
        dfs(root.rightChild, sought)
        return False

我用求值s创建的树如下：

n1 = Node()
n2 = Node()
n3 = Node()
n4 = Node()
n5 = Node()
n1.leftChild = n2
n1.rightChild = n5
n2.leftChild = n3
n2.rightChild = n4

n1.value=1
n2.value=2
n3.value=3
n4.value=4
n5.value=5

s = Node()
s.value=3

但输出令人困惑。我有一种预感 return True 的缺失与 Python 的递归性质有关？

> dfs(n1,s)
> root 1
> sought 3
> root 2
> sought 3
> root 3
> sought 3
> inside root = sought
> root 4
> sought 3
> root 5
> sought 3
> False

Answer 1

您需要return递归调用的结果：

    res_a = dfs(root.leftChild, sought)
    res_b = dfs(root.rightChild, sought)
    return res_a or res_b

Python 中的深度优先搜索从不 returns True

Depth-first search in Python never returns True

python

recursion

depth-first-search