701. 二叉搜索树中的插入操作
问题描述:给定二叉搜索树的根节点和一个要插入的值,将值插入到 BST 中并保持其性质。
思路:利用二叉搜索树左子树小于根节点、右子树大于根节点的有序性质。递归或迭代查找合适位置,若为空则创建新节点返回。
450. 删除二叉搜索树中的节点
问题描述:在 BST 中删除指定值的节点,并返回更新后的根节点。
思路:根据节点左右子树的情况分类处理。若无子节点直接删除;若有一个子节点用子节点替代;若有两个子节点,通常用右子树的最小值(或左子树的最大值)替换当前节点值,再删除该最小值节点。
669. 修剪二叉搜索树
问题描述:给定 BST 和边界范围 [low, high],修剪树使其所有节点值都在范围内。
思路:递归遍历。若当前节点值小于 low,说明左子树都不合法,返回右子树的修剪结果;若大于 high,返回左子树的修剪结果;否则保留当前节点,递归修剪左右子树。
108. 将有序数组转换为二叉搜索树
问题描述:将升序排列的整数数组转换为高度平衡的二叉搜索树。
思路:采用分治法。选取数组中间元素作为根节点,确保左右子树节点数尽可能相等。递归构建左右子树。
538. 把二叉搜索树转换为累加树
问题描述:给定 BST,将其转换为累加树,使每个节点的新值等于原树中大于或等于该节点值的所有节点值之和。
思路:利用 BST 的中序遍历特性(逆序遍历即从大到小)。维护一个全局累加变量,先访问右子树,再更新当前节点值,最后访问左子树。
总结:以上五个题目均围绕二叉搜索树的核心操作展开,重点考察对 BST 性质的理解以及递归遍历的应用。

