我无法用递归获取BST的特定节点，即每个栈都被擦除

Question

global nodeM
nodeM=None
def inorderTraversal(self, root: 'TreeNode', tval:int) -> 'TreeNode':
    #if(nodeM):
        #print("sdf", type(nodeM))
        #node=None
    if root:
       
        self.inorderTraversal(root.left,tval)
        print(root.val)
        if(root.val==tval):

            #print("root = ",root)
            
            nodeM=root
            print("node = ", nodeM)
            print("my MAN,", type(nodeM))
            return nodeM
            return #node

            #inorderTraversal(root.left,tval)
        self.inorderTraversal(root.right,tval)
        
        return

这是我每次尝试返回节点时的代码。如果这个节点是根节点，那就能正常工作；但如果不是根节点，它就会返回空值。问题在于，我要找的节点的值是tval，它肯定是存在的。

Answer 1

这里有几个问题：

• 虽然你有一个 return nodeM，但是在进行递归调用时你忽略了这个返回值。你调用了 self.inorderTraversal(root.left,tval)，但没有对这个调用的返回值做任何处理，而这个返回值可能就是你想找到的节点。对 self.inorderTraversal(root.right,tval) 也是一样。

• 使用全局变量并没有帮助，因为没有任何代码会去读取 nodeM 的值（除了打印它）。而且，它只被设置为 None 一次，所以如果你进行多次树的遍历，nodeM 可能仍然会保留之前遍历树的节点引用。因此，最好不要使用全局变量，这并不是必须的。

以下是修改后的代码，并在更改的地方添加了注释：

class Solution:
    def inorderTraversal(self, root: 'TreeNode', tval:int) -> 'TreeNode':
        if root:
            result = self.inorderTraversal(root.left, tval)
            if result:  # Should check if the recursive call had success
                return result
            if root.val == tval:
                # Don't use a global variable: only return the match
                return root
            result = self.inorderTraversal(root.right,tval)
            if result:  # Should check if the recursive call had success
                return result

你也可以用一个 return 表达式来实现这个：

class Solution:
    def inorderTraversal(self, root: 'TreeNode', tval:int) -> 'TreeNode':
        return root and (
            root if root.val == tval else (
                self.inorderTraversal(root.left, tval) or
                self.inorderTraversal(root.right,tval)
            )
        )

还有一点需要说明的是：在你帖子标题中提到的“BST”让人感到困惑，因为如果你的树只是任何一种二叉树，而不一定是二叉搜索树，那么就需要进行完整的遍历。如果你的树确实是二叉搜索树，那么就不应该进行中序遍历。二叉搜索树的理念是你有更快的方法来找到一个节点，你只需要朝一个方向查找，而不必同时查看左边和右边。如果你确实想在二叉搜索树中搜索，可以查看 在二叉搜索树中搜索。

Answer 2

在trincot的回答中已经详细分析了你代码中的问题，这里我想用更简单的方式来解释，并提供一个关于二叉树遍历的例子，同时也讲讲如何使用逻辑运算符and和or。在Python中，这两个运算符并不会直接返回True或False，而是返回表达式中某个部分的值。

你提到的问题的根本原因在于，你期望初始调用的遍历函数会返回找到的节点，但对于根节点的情况是没有递归的。这种做法并没有按预期工作，因为在你的代码中，深层递归函数调用返回的值并没有传递回上层调用的函数。

请注意，你问题中的代码总是遍历整个树。我稍微调整了一下代码，让它在找到节点后停止进一步搜索，并且解决了不返回找到节点的问题，使用了一个全局变量。在我看来，这种方法比trincot建议的聪明使用返回值更容易理解。

下面的代码中有更多的解释作为注释：

import collections

foundNode=None
def inorderTraversal1(node, tval):
    global foundNode
    if   node is not None   and   foundNode is None:
        print( node.val )
        if(node.val==tval):
            print("nodeValue = ", node.val)
            print("nodeType", type(node))
            foundNode=node
        else: # the node has other node.val as tval, so check its sub-nodes: 
            inorderTraversal1(node.left,tval)
            if foundNode is None: 
                inorderTraversal1(node.right,tval)  

def inorderTraversal2( root, tval ):
    return root and ( 
# NOTICE that logical   and   does not return True/False but the first component
#   which evaluates to False, or the last component if all evaluate to True
        root if root.val == tval else (
            inorderTraversal2(root.left, tval) 
            or
            inorderTraversal2(root.right,tval)
# NOTICE that logical   or   does not return True/False but the first item
#   which evaluates to True, or the last item if all evaluate to False
    )
)

BTnode = collections.namedtuple('BTnode', ['left', 'right', 'val'])
root=BTnode( val='0',
    left=BTnode( val='01',
        left=BTnode( val='011',
            left=BTnode( val='0111', left=None, right=None ),
            right=BTnode( val='0112',
                left=BTnode(val='01121', left=None, right=None ),
                right=BTnode( val='01122', left=None, right=None )
            )
        ),
        right=BTnode( val='012', left=None, right=None  )
    ),
    right=BTnode( val='02',
        left=BTnode( val='021', left=None, right=None ),
        right=BTnode( val='022', left=None,     right=None  )
    )
)

foundNode=None; inorderTraversal1(root, '022') # !!! WATCH OUT !!!
#        ^-- initialize `foundNode=None` in front of every call
#                of `inorderTraversal1()`
print(foundNode)
print( " ----- " )
print( inorderTraversal2(root, '022') )
print("===============")
foundNode=None; inorderTraversal1(root, '01122')
print(foundNode)
print( " ----- " )
print( inorderTraversal2(root, '01122') )

输出结果为：

> cd /home/o/oOo/O@@/stackoverflow
> python3 -u "BTree.py"
0
01
011
0111
0112
01121
01122
012
02
021
022
nodeValue =  022
nodeType <class '__main__.BTnode'>
BTnode(left=None, right=None, val='022')
 ----- 
BTnode(left=None, right=None, val='022')
===============
0
01
011
0111
0112
01121
01122
nodeValue =  01122
nodeType <class '__main__.BTnode'>
BTnode(left=None, right=None, val='01122')
 ----- 
BTnode(left=None, right=None, val='01122')
> exit status: 0