求助：从给定前序遍历BST数组获取叶子节点的程序仅输出首个节点

嘿，我碰到过类似的问题！你的程序只输出第一个叶子节点，大概率是两个地方出了问题——要么是遍历叶子节点的递归逻辑提前终止了，要么是从先序数组构建BST的过程出错了，导致树的结构不对。我来给你拆解一下：

1. 最常见的坑：遍历函数里多余的return #

很多人写递归找叶子的时候，找到第一个叶子打印后就直接return了，这会导致后续的遍历被中断，自然找不到其他叶子。比如你可能写了这样的代码：

def print_leaves(node):
    if not node:
        return
    # 找到叶子节点就打印，但这里的return会直接结束函数！
    if not node.left and not node.right:
        print(node.val)
        return  # 就是这个return搞的鬼！
    print_leaves(node.left)
    print_leaves(node.right)

修正方法：把那个多余的return删掉就行！这样当找到叶子打印后，函数会继续执行后续的递归，遍历左子树和右子树的其他节点：

def print_leaves(node):
    if not node:
        return
    if not node.left and not node.right:
        print(node.val)
        # 这里不要return，让函数继续往下走
    print_leaves(node.left)
    print_leaves(node.right)

2. 另一个可能：BST构建错误 #

如果你的BST构建逻辑有问题，比如只构建了左子树或者右子树，那树本身就只有一个叶子节点，自然只能输出一个。比如错误的构建代码：

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

def build_bst_from_preorder(preorder):
    if not preorder:
        return None
    root = TreeNode(preorder[0])
    # 错误：把所有后续元素都当成左子树，完全没处理右子树
    root.left = build_bst_from_preorder(preorder[1:])
    return root

正确的先序构建BST逻辑：先序遍历的第一个元素是根，然后找到第一个比根大的元素，左边的是左子树的先序数组，右边的是右子树的先序数组，递归构建：

def build_bst_from_preorder(preorder):
    if not preorder:
        return None
    root = TreeNode(preorder[0])
    # 找到第一个大于根节点值的索引，划分左右子树
    split_idx = 1
    while split_idx < len(preorder) and preorder[split_idx] < root.val:
        split_idx += 1
    # 构建左子树和右子树
    root.left = build_bst_from_preorder(preorder[1:split_idx])
    root.right = build_bst_from_preorder(preorder[split_idx:])
    return root

验证一下 #

比如拿测试用例先序数组[8,5,1,7,10,12]，对应的BST叶子节点是1、7、12。用修正后的代码跑，就能输出这三个值啦！

你可以先检查自己的遍历函数有没有提前return，再检查BST的构建逻辑，应该就能解决问题了～

内容的提问来源于stack exchange，提问作者Jay.Rana