🙊 前言：本文章为瑞_系列专栏之《刷题》的力扣LeetCode系列，主要以力扣LeetCode网的题进行解析与分享。本文仅供大家交流、学习及研究使用，禁止用于商业用途，违者必究！

说明

  本文主要是配合《瑞_数据结构与算法_二叉搜索树》对二叉搜索树的知识进行提升和拓展，力扣中的树节点 TreeNode 相当于《瑞_数据结构与算法_二叉搜索树》中的 BSTNode，区别在于：

• TreeNode（力扣）属性有：val, left, right，并未区分键值
• BSTNode 属性有：key, value, left, right，区分了键值

  TreeNode类（力扣）：

/**
 * 力扣用到的二叉搜索树节点
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return String.valueOf(val);
    }
}

  BSTNode类：

/**
 * 二叉搜索树, 泛型 key 版本
 */
public class BSTTree2<K extends Comparable<K>, V> {

    static class BSTNode<K, V> {
        // 索引(泛型)，比较值
        K key;
        // 该节点的存储值(泛型)
        V value;
        // 左孩子
        BSTNode<K, V> left;
        // 右孩子
        BSTNode<K, V> right;

        public BSTNode(K key) {
            this.key = key;
        }

        public BSTNode(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(K key, V value, BSTNode<K, V> left, BSTNode<K, V> right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    // 根节点
    BSTNode<K, V> root;
}

  所以力扣的 TreeNode 没有 key，比较二叉树节点用的是 TreeNode.val 属性与待删除 key 进行比较，因为力扣主要是练习题，对实际情况进行了简化

题目 450. 删除二叉搜索树中的节点

  原题链接：450. 删除二叉搜索树中的节点

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

  一般来说，删除节点可分为两个步骤：
  1️⃣首先找到需要删除的节点；
  2️⃣如果找到了，删除它。

  示例1：

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

  示例2：

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

  示例3：

输入: root = [], key = 0
输出: []

  提示:

• 节点数的范围[0, 10⁴].
• -10⁵ <= Node.val <= 10⁵
• 节点值唯一
• root 是合法的二叉搜索树
• -10⁵ <= key <= 10⁵

  进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。

题解

  删除remove(int key)方法需要考虑的情况较多。要删除某节点（称为 D），必须先找到被删除节点的父节点，这里称为 Parent，具体情况如下：

1. 删除节点没有左孩子，将右孩子托孤给 Parent
2. 删除节点没有右孩子，将左孩子托孤给 Parent
3. 删除节点左右孩子都没有，已经被涵盖在情况1、情况2 当中，把 null 托孤给 Parent
4. 删除节点左右孩子都有，可以将它的后继节点（称为 S）托孤给 Parent，设 S 的父亲为 SP，又分两种情况
   1. SP 就是被删除节点，此时 D 与 S 紧邻，只需将 S 托孤给 Parent
   2. SP 不是被删除节点，此时 D 与 S 不相邻，此时需要将 S 的后代托孤给 SP，再将 S 托孤给 Parent

  删除本身很简单，只要通过索引查找到该节点删除即可，但是，由于需要料理后事，所以想要做好删除操作，需要处理好“托孤”操作。

递归实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode node, int key) {
        if (node == null) {
            return null;
        }
        if (key < node.val) { // 没找到，继续递归调用
            node.left = deleteNode(node.left, key);
            return node;
        }
        if (node.val < key) { // 没找到，继续递归调用
            node.right = deleteNode(node.right, key);
            return node;
        }
        if (node.left == null) { // 情况1 - 只有右孩子
            return node.right;
        }
        if (node.right == null) { // 情况2 - 只有左孩子
            return node.left;
        }
        TreeNode s = node.right; // 情况3 - 有两个孩子
        while (s.left != null) {
            s = s.left;
        }
        s.right = deleteNode(node.right, s.val);
        s.left = node.left;
        return s;
    }
}

题目 701. 二叉搜索树中的插入操作

  原题链接：701. 二叉搜索树中的插入操作

  给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

  注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

  示例1：

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

  示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

  示例 3：

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

  提示：

• 树中的节点数将在 [0, 10⁴]的范围内。
• -10⁸ <= Node.val <= 10⁸
• 所有值 Node.val 是 独一无二 的。
• -10⁸ <= val <= 10⁸
• 保证 val 在原始BST中不存在。

题解

  分为两种情况：

  1️⃣ key在整个树中已经存在，新增操作变为更新操作，将旧的值替换为新的值
  2️⃣ key在整个树中未存在，执行新增操作，将key value添加到树中

  由于题目中的前提是：保证 val 在原始BST中不存在。因此只需考虑新增情况，不会出现更新情况

递归实现

• 若找到 key，走 else 更新找到节点的值
• 若没找到 key，走第一个 if，创建并返回新节点
  • 返回的新节点，作为上次递归时 node 的左孩子或右孩子

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode node, int val) {
        if (node == null) {
            return new TreeNode(val);
        }
        if (val < node.val) {
            node.left = insertIntoBST(node.left, val);
        } else if (node.val < val) {
            node.right = insertIntoBST(node.right, val);
        }
        return node;
    }
}

  此处return node返回当前节点会多出一些额外的赋值动作。如下面这颗二叉搜索树，1作为插入节点，1和2通过node.left = insertIntoBST(node.left, val);建立父子关系返回，这是有必要的，但是由于递归，2和5也会通过node.left = insertIntoBST(node.left, val);建立父子关系，这样就是没必要的（因为5和2原本就存在父子关系），如果树的深度很大，那就会浪费很多性能。

        5
       / \
      2   6
        \   \
    1    3   7

题目 700. 二叉搜索树中的搜索

  原题链接：700. 二叉搜索树中的搜索

  给定二叉搜索树（BST）的根节点root和一个整数值val。

  你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

  示例1：

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

  示例2：

输入：root = [4,2,7,1,3], val = 5
输出：[]

  提示：

• 树中节点数在 [1, 5000] 范围内
• 1 <= Node.val <= 107
• root 是二叉搜索树
• 1 <= val <= 10⁷

题解

递归实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode node, int val) {
        if (node == null) {
            return null;
        }
        if (val < node.val) {
            return searchBST(node.left, val);
        } else if (node.val < val) {
            return searchBST(node.right, val);
        } else {
            return node;
        }
    }
}

题目 98. 验证二叉搜索树

  原题链接：98. 验证二叉搜索树

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

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

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

  示例 1：

输入：root = [2,1,3]
输出：true

  示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

  提示：

• 树中节点数目范围在[1, 10⁴] 内
• -2³¹ <= Node.val <= 2³¹ - 1

题解

  合法的二叉搜索树即左边的都更小，右边的都更大，如下，第一个的树为合法二叉搜索树，而第二、三（等于也是非法的）均不合法

         4			  5		      1
       /   \		/   \			\
      2     6	   4     6            1
     / \			   /   \	
    1   3			  3     7

  思路：利用二叉树中序遍历的特性（遍历后是升序的结果），所以遍历的结果一定是一个由小到大的结果，以此判断是否合法

瑞：关于二叉树中序遍历，可以参考《瑞_数据结构与算法_二叉树》

中序遍历非递归实现

public boolean isValidBST(TreeNode root) {
    TreeNode p = root;
    LinkedList<TreeNode> stack = new LinkedList<>();
    // 代表上一个值
    long prev = Long.MIN_VALUE;
    while (p != null || !stack.isEmpty()) {
        if (p != null) {
            stack.push(p);
            p = p.left;
        } else {
            TreeNode pop = stack.pop();
            // 处理值，上一个值大于等于当前值的时候是非法二叉搜索树
            if (prev >= pop.val) {
                return false;
            }
            // 更新值
            prev = pop.val;
            p = pop.right;
        }
    }
    return true;
}

  记录 prev 需要用 long，否则若测试用例中最小的节点为 Integer.MIN_VALUE 则测试会失败

中序遍历递归实现

  使用递归的时候为避免性能浪费，可以进行剪枝操作。要注意在递归的时候不能用 Long 或 long，因为它们都是局部变量且不可变，因此每次赋值时，并不会改变其它方法调用时的 prev，所以要把 prev 设置为全局变量

    // 全局变量记录 prev
    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode node) {
        if (node == null) {
            return true;
        }
        boolean a = isValidBST(node.left);
        // 剪枝
        if (!a) {
            return false;
        }
        // 处理值
        if (prev >= node.val) {
            return false;
        }
        prev = node.val;
        return isValidBST(node.right);
    }

  瑞：以上代码在力扣中运行的时间是0ms，竟然优于中序遍历非递归实现的1ms，这里理论上说不过去，毕竟递归应该更耗费性能，但有可能由于力扣对栈的使用有自己的判定方式，所以可能造成这样的运行结果，但是理论上应该是非递归效率更好

上下限递归

  可以对每个节点增加上下限，使用上限下限来递归判断。

• 根节点的下限是-∞，上限是+∞
• 根节点的左孩子的下限是-∞，上限是根节点值
• 根节点的右孩子的下限是根节点值，上限是上限是+∞
• 以此递归

public boolean isValidBST(TreeNode node) {
    return doValid(node, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean doValid(TreeNode node, long min, long max) {
    if (node == null) {
        return true;
    }
    if (node.val <= min || node.val >= max) {
        return false;
    }
    return doValid(node.left, min, node.val) && doValid(node.right, node.val, max);
}

• 设每个节点必须在一个范围内：$(min,max)$，不包含边界，若节点值超过这个范围，则返回 false
• 对于 node.left 范围肯定是 $(min,node.val)$
• 对于 node.right 范围肯定是 $(node.val,max)$
• 一开始不知道 min，max 则取 java 中长整数的最小、最大值
• 本质是前序遍历 + 剪枝

---

本文是博主的粗浅理解，可能存在一些错误或不完善之处，如有遗漏或错误欢迎各位补充，谢谢

  如果觉得这篇文章对您有所帮助的话，请动动小手点波关注💗，你的点赞👍收藏⭐️转发🔗评论📝都是对博主最好的支持~