Python中预排序二叉搜索树的叶节点
内容提要
二叉树是一种包含不同节点的数据结构，每个节点最多有两个子节点。遍历二叉搜索树的方法有前序、中序和后序。给定一个二叉搜索树的前序，需要打印叶节点。通过中序数组和前序数组查找二叉搜索树的前序，然后打印叶节点。另一种方法是使用堆栈遍历数组，找到叶节点并打印。
延伸解读
两种解法对比：递归与栈
文章介绍了两种从二叉搜索树前序序列中提取叶节点的方法。第一种方法先通过排序前序序列得到中序序列，然后递归地利用二分查找定位根节点，从而划分左右子树并识别叶节点。第二种方法使用栈和双指针遍历前序序列，通过比较元素大小关系直接判断叶节点。前者逻辑清晰但需要额外排序和递归栈空间；后者一次遍历即可完成，空间效率更高，但实现细节更需谨慎。
叶节点判断的关键逻辑
在递归方法中，叶节点的判断依据是中序序列中当前子树区间左右边界相等（即 ln == rn），此时该位置对应一个没有子节点的节点。在栈方法中，叶节点则通过比较当前元素与栈顶元素的关系来识别：当遇到比栈顶大的元素时，弹出栈顶并标记前一个元素为叶节点。理解这些判断条件是正确实现算法的核心，否则可能遗漏或误判叶节点。
输入序列的隐含要求
文章强调所有节点值都是正数且已经预先排序，但这里的“预先排序”应理解为前序序列本身符合二叉搜索树的前序遍历顺序，而非数值有序。实际上，前序序列的第一个元素是根，后续元素按“根-左-右”排列。读者需注意，算法依赖于二叉搜索树的性质：左子树所有节点值小于根，右子树所有节点值大于根。若输入不满足此性质，则输出可能错误。
Q&A
给定二叉搜索树的前序遍历，如何打印出所有叶节点？
有两种方法：1. 简单方法：利用前序和中序数组，通过二分搜索递归找到叶节点并打印。2. 使用堆栈：遍历前序数组，用堆栈辅助判断叶节点并打印。
使用中序数组和前序数组查找叶节点的具体步骤是什么？
首先对前序数组排序得到中序数组。然后递归处理：在当前中序范围[ln, rn]中，如果ln等于rn，则当前节点是叶节点，打印；否则，在前序中取当前根节点值，在中序中二分查找其位置loc，然后递归处理左子树[ln, loc-1]和右子树[loc+1, rn]。
如何使用堆栈方法从BST前序中打印叶节点？
使用两个指针i和j遍历前序数组。初始化空堆栈。对于j从1到n-1：如果preorder[i] > preorder[j]，将preorder[i]压栈；否则，当堆栈非空且preorder[j] > 栈顶时，弹出栈顶并标记found；如果found为真，则打印preorder[i]。最后打印preorder[n-1]。
给定前序序列{300, 224, 125, 70, 149, 388}，叶节点是什么？
叶节点是70, 149, 388。
给定前序序列{42, 30, 27, 23, 19, 22, 26, 29, 15, 32, 31, 35, 38}，叶节点是什么？
叶节点是15, 22, 26, 29, 31, 38。
二叉搜索树有哪些遍历方式？
二叉搜索树的遍历方式包括：中序（左-根-右）、前序（根-左-右）和后序（左-右-根）。
