Python中的深度優先搜索從未返回True

Question

在明確包含3的樹中搜索「3」時，代碼將進入正確的「if語句」，但不會返回True。這是爲什麼？

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

您需要從遞歸調用返回的結果：

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