我无法使用递归获取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

这是每次我尝试返回节点时的代码，如果它是根节点，则它可以工作，否则它返回 null-none。问题是找到tval的节点，它肯定存在

Answer 1

有几个问题：

• 尽管您有一个

  return nodeM

  ，但在进行递归调用时您会忽略此返回值。你有

  self.inorderTraversal(root.left,tval)

  ，但不要对这个调用的 returns 做任何事情，但该返回可能是找到的节点。

  self.inorderTraversal(root.right,tval)

  也是如此

• 使用全局变量没有帮助，因为没有代码可以读取

  nodeM

  的值（除了打印它）。此外，它仅设置为

  None

  一次，因此，如果您进行多次树遍历，

  nodeM

  可能仍然具有来自 previous 迭代树的节点引用。所以不要使用全局变量。不需要。

更正了带有更改的注释的代码：

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

还有一点：在你的帖子标题中你提到了“BST”。这很令人困惑，因为只有当你的树只是any二叉树，而不一定是 BST 时，才需要完全遍历。然而，如果您的树是 BST，那么您不应该执行中序遍历。 BST 的想法是让你有一种更快的方法来找到一个节点，而且你不必左顾右盼，而只走单向。如果实际上您想搜索 BST，请查看 在二叉搜索树中搜索