BST节点Inorder Successor函数报错：部分节点出现AttributeError排查

我正在解决GeeksforGeeks上的《Inorder Successor in BST》问题，题目要求给定一棵BST和其中的节点x，找到该节点的中序后继。我参考了从根节点搜索（无需父指针）的方法实现代码，但运行时发现，针对n4、n10这类节点调用inorder_successor函数时，返回None并触发“'NoneType' object has no attribute 'elem'”错误，而n8、n20这类节点则能正常运行。我尝试在代码中打印相关节点的elem属性能得到正确值，但函数返回结果异常，现需排查代码中的错误原因。

以下是我的实现代码及测试用例：

def inorder_successor(root, x):
  if x.right != None :
      t = x.right 
      while t.left != None:
        t = t.left
        #print(t.elem)
      return t  
  if root.left == None or root.right:
    return
  if root.left == x:
    return root 

  inorder_successor(root.left, x)
  inorder_successor(root.right, x)
  
def inorder(root):
  if root == None:
    return

  inorder(root.left)
  print(root.elem, end = ' ')
  inorder(root.right)
  
class BTNode:
  def __init__(self, elem):
    self.elem = elem
    self.right = None
    self.left = None

# Create input BST    
n20 = BTNode(20)
n8  = BTNode(8)
n22 = BTNode(22)
n4  = BTNode(4)
n12 = BTNode(12)
n10 = BTNode(10)
n14 = BTNode(14)

n20.left = n8
n20.right = n22

n8.left = n4
n8.right = n12

n12.left = n10
n12.right = n14

print('Given Tree Inorder Traversal: ', end = ' ')
inorder(n20) #Given Tree Inorder Traversal:  4 8 10 12 14 20 22
print()

# This works:
x = n8
print(f'Inorder successor of node {x.elem}: {inorder_successor(n20, x).elem}') #Inorder successor of node 8: 10

# This doesn't work (None). Expected 8
x = n4
print(f'Inorder successor of node {x.elem}: {inorder_successor(n20, x).elem}')  # Error

测试用的BST结构如下：

20
    /  \
   8    22
  / \
 4   12
    /  \
  10    14

错误原因分析 #

1. 递归调用未返回结果：在递归遍历左右子树时，你调用了inorder_successor(root.left, x)和inorder_successor(root.right, x)，但没有把递归的返回值传递出去。这导致当后继节点在子树中找到时，结果无法向上传递，最终函数返回None。
2. 条件判断逻辑错误：if root.left == None or root.right:这个条件完全不符合需求，它的含义是“如果根节点左子为空，或者根节点有右子”就直接返回None，这会提前终止正确的搜索路径。比如找n4的后继时，遍历到root为n8时，这个条件会触发（因为n8有右子），直接返回None，而不会执行后续判断root.left == x的逻辑。

修正后的代码 #

def inorder_successor(root, x):
    # 情况1：x有右子树，后继是右子树的最左节点
    if x.right is not None:
        t = x.right
        while t.left is not None:
            t = t.left
        return t
    
    # 情况2：x没有右子树，从根往下找最近的祖先，该祖先的左子树包含x
    successor = None
    current = root
    while current is not None:
        if x.elem < current.elem:
            successor = current
            current = current.left
        elif x.elem > current.elem:
            current = current.right
        else:
            break
    return successor

def inorder(root):
  if root == None:
    return

  inorder(root.left)
  print(root.elem, end = ' ')
  inorder(root.right)
  
class BTNode:
  def __init__(self, elem):
    self.elem = elem
    self.right = None
    self.left = None

# Create input BST    
n20 = BTNode(20)
n8  = BTNode(8)
n22 = BTNode(22)
n4  = BTNode(4)
n12 = BTNode(12)
n10 = BTNode(10)
n14 = BTNode(14)

n20.left = n8
n20.right = n22

n8.left = n4
n8.right = n12

n12.left = n10
n12.right = n14

print('Given Tree Inorder Traversal: ', end = ' ')
inorder(n20)
print()

# 正常运行
x = n8
print(f'Inorder successor of node {x.elem}: {inorder_successor(n20, x).elem}')

# 现在正常返回8
x = n4
print(f'Inorder successor of node {x.elem}: {inorder_successor(n20, x).elem}')

# 测试n10，返回12
x = n10
print(f'Inorder successor of node {x.elem}: {inorder_successor(n20, x).elem}')

修正说明 #

• 移除了错误的条件判断，改用迭代方式从根节点搜索，避免递归返回值丢失的问题，逻辑更清晰。
• 针对x没有右子树的场景，利用BST的性质：中序后继是第一个比x值大的祖先节点。遍历过程中记录遇到的符合条件的祖先，最终得到的就是正确的后继节点。

内容的提问来源于stack exchange，提问作者Rodel Advan