Python递归函数无法返回数组：BST节点路径查找失败求助

问题原因 #

你的代码存在三个关键错误，导致无法得到预期路径：

• 初始路径重复添加根节点：调用时传入[root]作为初始路径，递归中又会再次将root加入路径，导致路径出现重复节点。
• 目标节点未被加入路径：找到目标节点时直接返回现有路径，没有把目标节点本身包含进去。
• 节点添加时机逻辑混乱：在移动到子节点前错误地重复添加当前节点。

修正后的代码 #

推荐实现（逻辑统一版） #

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 构建二叉搜索树
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(8)
root.left.left = TreeNode(0)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(3)
root.left.right.right = TreeNode(5)
root.right.left = TreeNode(7)
root.right.right = TreeNode(9)

p = 2
q = 8

def pathFind(path, cur, target_val):
    # 先将当前节点加入路径
    path.append(cur)
    
    # 找到目标节点，返回完整路径
    if cur.val == target_val:
        return path
    
    # 利用BST特性：目标值更大则走右子树
    if cur.val < target_val:
        return pathFind(path, cur.right, target_val)
    # 目标值更小则走左子树
    else:
        return pathFind(path, cur.left, target_val)

# 初始传入空路径，从根节点开始查找
path_p = pathFind([], root, p)
# 打印路径节点值验证
print([node.val for node in path_p])  # 输出: [6, 2]

适配原初始调用的版本 #

如果坚持要保留pathFind([root], root, p)的调用方式，可以这样修改：

def pathFind(path, cur, target_val):
    if cur.val == target_val:
        return path
    
    # 根据BST特性选择子树，并将子节点加入路径
    next_node = cur.right if cur.val < target_val else cur.left
    path.append(next_node)
    return pathFind(path, next_node, target_val)

path_p = pathFind([root], root, p)
print([node.val for node in path_p])  # 输出: [6, 2]

修改说明 #

1. 统一节点添加逻辑：推荐初始传入空路径，在递归函数第一步就将当前节点加入路径，确保所有经过的节点（包括目标节点）都被正确记录，避免重复或遗漏。
2. 简化判断逻辑：由于题目保证目标节点存在，无需额外判断子节点是否为空，直接利用BST的左小右大特性走向对应子树即可。
3. 修正目标节点的记录：确保找到目标时，节点已经被加入路径（或在适配版本中，初始路径已包含根节点，后续只添加子节点直到目标）。

内容的提问来源于stack exchange，提问作者Junyeong Ahn