LeetCode Binary Search Tree 刷题模板
内容提要
二叉搜索树（BST）是一种有序树结构，节点值左小右大。中序遍历可获取排序后的节点值，常见题目如求最小绝对差和第K小元素可通过中序遍历快速解决。构建BST可用递归分治法，验证BST有效性需检查所有子树节点值是否符合规则。
延伸解读
中序遍历模板的通用性
文章提供的迭代式中序遍历模板使用栈模拟递归，能高效获取BST的有序节点值。该模板不仅适用于最小绝对差和第K小元素问题，还可用于其他需要有序序列的BST题目。掌握此模板可避免重复编写递归代码，提高刷题效率。
第K小元素的优化思路
基础解法先获取完整有序数组再取第k个元素，空间和时间复杂度均为O(n)。优化解法在遍历过程中计数，当遍历到第k个节点时立即返回，无需存储整个数组，将空间复杂度降至O(h)（h为树高），适合k较小的情况。
验证BST的常见陷阱
仅比较节点与直接子节点的大小关系会遗漏更深层子树的约束，导致错误判断。正确做法是使用上下界（low, hi）递归验证，确保左子树所有节点小于当前节点，右子树所有节点大于当前节点。边界初始值应使用64位最小/最大值以避免节点值溢出。
构建BST的分治策略
将有序数组转换为平衡BST时，选择中间元素作为根节点可保证左右子树高度差不超过1。递归处理左右子数组时，需注意边界条件（left > right时返回nil）。此方法时间复杂度O(n)，空间复杂度O(log n)（递归栈深度）。
Q&A
什么是二叉搜索树（BST）？
二叉搜索树（BST）是一种有序树结构，节点值左小右大。
如何通过中序遍历获取二叉搜索树的节点值？
通过中序遍历，可以访问树的各个节点，最终得到一个有序的数组。
如何构建一个二叉搜索树？
构建BST可用递归分治法，将数组中间元素作为根节点，左右部分递归构建子树。
如何验证一个二叉树是否为有效的二叉搜索树？
验证BST有效性需检查所有子树节点值是否符合规则，使用边界值来判断。
求二叉搜索树的最小绝对差的解法是什么？
使用中序遍历获得排序后的节点值，遍历计算两个数之间的差值，更新最小差值。
如何找到二叉搜索树中的第K小元素？
使用中序遍历获得排序后的节点值，直接返回第k个元素。
