代码随想录算法训练营第16-20天｜二叉树Part04-07

记录题目：

• 验证二叉搜索树
• 二叉搜索树的最小绝对差
• 删除二叉搜索树中的节点

给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

• 节点的左子树只包含小于当前节点的数。

• 节点的右子树只包含大于当前节点的数。

• 所有左子树和右子树自身必须也是二叉搜索树。

LeetCode98. 验证二叉搜索树

中序遍历下，输出的二叉搜索树节点的数值是有序序列。

有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。 差值是一个正数，其数值等于两值之差的绝对值。

LeetCode530. 二叉搜索树的最小绝对差

二叉搜索树采用中序遍历时其实就是一个有序数组，在一个二叉搜索树上寻找最值、差值的问题，其实就相当于在有序数组上求最值、差值。

对于本题最直观的想法，就是把二叉搜索树转换成有序数组，然后遍历一遍数组统计出来最小差值。 但其实在二叉搜索树中序遍历的过程中，是可以直接计算的，只需要在递归函数外部使用变量记录前一个节点即可。

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

LeetCode450. 删除二叉搜索树中的节点

这道题目主要涉及到如下两大方面：

1. 如何在 BST 中找到要删除的目标节点；
2. 找到目标节点后，如何删除它，并保持 BST 的结构性质不变。

删除节点的三种基本情况

若目标节点存在，删除时需分情况处理：

1. 该节点是叶子节点：直接删除，返回 null；

2. 该节点只有一个子节点：将其子节点接上父节点；

3. 该节点有两个子节点：

   • 找到右子树中的最小节点（中序后继）；
   • 用其值替换当前节点；
   • 在右子树中递归删除这个最小节点。

递归删除的本质优势

该题递归实现优于手动寻找父节点的写法，具有如下优势：

1. 避免记录父节点：递归时每次返回的值就是“当前子树删除目标节点后的新子树根”，上层调用自然完成连接更新，无需显式保存父节点指针。

2. 处理逻辑在一次遍历中完成：递归调用过程即自顶向下查找节点，自底向上重建子树结构，不需要“先找目标节点再找其父节点”的两次遍历。

3. 不需特殊处理根节点：根节点若正是要删除的节点，只需返回新的根节点即可，递归天然适配这一情形。

结构更新的函数式范式

递归方式将子问题抽象为“删除后返回新的子树根节点”，上层直接接收作为左或右子树的更新结果，无需外部修改或标记。

标准递归实现

var deleteNode = function(root, key) {
    if (!root) return null;
    if (key < root.val) {
        // 去左子树找目标节点
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        // 去右子树找目标节点
        root.right = deleteNode(root.right, key);
    } else {
        // 找到目标节点，开始删除
        if (!root.left && !root.right) {
            // 1. 无子节点
            return null;
        } else if (!root.left || !root.right) {
            // 2. 只有一个子节点
            return root.left || root.right;
        } else {
            // 3. 有两个子节点
            const minNode = getMin(root.right);
            root.val = minNode.val; // 用右子树最小节点的值替代
            root.right = deleteNode(root.right, minNode.val); // 删除该最小节点
        }
    }
    return root;
};
// 获取右子树最小节点
function getMin(node) {
    while (node.left) node = node.left;
    return node;
}

设计上的启发

1. 凡是需要“在递归中操作树结构”的问题，都可以采用“返回新的子树根”这一模式，代替显式父节点操作；
2. 当节点结构不变但需要局部更新时，返回值就是“子树更新结果”；
3. 使用中序后继（右子树最小）或中序前驱（左子树最大）都可以替代节点值，保持 BST 性质，前者更常见；
4. 若允许重复值，则应定义“删除策略”（如优先删除左子树中的某个值）；
5. 若采用非递归方式，通常需要显式追踪父节点或构造 dummy 节点模拟根节点处理。