簡單樹遍歷：幫我調試

Question

這是我怎麼會遍歷二叉樹在Python

def binary_tree(root): 
    if root.left: 
    binary_tree(root.left) 
    print root 
    if root.right: 
    binary_tree(root.right) 

，如果我需要返回通過路徑：

def binary_tree(node, path): 
    if root.left: 
    binary_tree(root.left) 
    path.append(root) 
    if root.right: 
    binary_tree(root.right) 
    return path 

好了，很容易的。我對樹遍歷有信心，所以我嘗試以下。

def nary_tree(root, value): 
    """return True if there is a node with value exists in root""" 
    if not root: #empty tree 
     return False 
    if root.left: 
     nary_tree(root.left, value) 
    if root.data == value: #recurse up until the current node has a right child 
     return True 
    if root.right: 
     nary_tree(root.right, value) 
    return False 

這應該不會返回True。所以我嘗試調試，進入功能。我意識到我不應該通過返回一個值來逃避遞歸。上面的代碼會多次返回True一次和False，如果有匹配的節點，我幾乎總是會得到一個False。所以我嘗試以下方法：

def nary_tree(root, value): 
    """return True if there is a node with value exists in root""" 
    if not root: #empty tree 
     return False 
    if root.left: 
     return nary_tree(root.left, value) 
    if root.data == value: 
     #but in this case, this is never executed 
     return True 
    if root.right: 
     return nary_tree(root.right, value) 
    return False #how was this being executed in above example then? 

問題：

1. 我是什麼誤會？
2. 你會如何解決上面的代碼？

我在編寫遞歸函數時相當舒服，但我似乎仍然感到困惑。

Answer 1

即使當前節點有數據，如果它有一個左節點，您將從該函數返回。理想情況下，這本來應該是這樣的

def nary_tree(root, value): 
    """return True if there is a node with value exists in root""" 
    if not root: #empty tree 
     return False 
    if root.data == value: 
     return True 
    if nary_tree(root.left, value): 
     return True 
    if nary_tree(root.right, value): 
     return True 
    return False #how was this being executed in above example then?