思路：labuladong

基本框架

void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

98 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 * * 有效 二叉搜索树定义如下： * * * 节点的左子树只包含 小于 当前节点的数。 * 节点的右子树只包含 大于 当前节点的数。 * 所有左子树和右子树自身必须也是二叉搜索树。   * 示例 1：   * 输入：root = [2,1,3] * 输出：true * * * 示例 2： * * * 输入：root = [5,1,4,null,null,3,6] * 输出：false * 解释：根节点的值是 5 ，但是右子节点的值是 4 。   * 提示：树中节点数目范围在[1, 10^4] 内 * -2^31 <= Node.val <= 2^31 - 1   思路： 二叉搜索树一方面左结点<根节点<右结点，同时要满足左子树整体<根节点<右子树 因此遍历时要引入最大最小值，然后在比较左右结点时还有判断最大最小值  

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return traverse(root, nullptr,nullptr);
    }
    bool traverse(TreeNode* root,TreeNode* min,TreeNode* max){
        if(root==nullptr) return true;
        if(min!=nullptr&&root->val<=min->val) return false;
        if(max!=nullptr&&root->val>=max->val) return false;
        return traverse(root->left,min,root)&&traverse(root->right,root,max);
    }
};

700. 二叉搜索树中的搜索（简单）

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。 * * 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。   * 示例 1: * 输入：root = [4,2,7,1,3], val = 2 * 输出：[2,1,3] * * * Example 2: * 输入：root = [4,2,7,1,3], val = 5 * 输出：[]   * 提示： * 数中节点数在 [1, 5000] 范围内 * 1 <= Node.val <= 10^7 * root 是二叉搜索树 * 1 <= val <= 10^7   思路： 利用二分查找的思路，大于root就在右子树找，小于root就在左子树找  

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root==nullptr) return root;
        if(root->val==val) return root;
        if(root->valreturn searchBST(root->right,val);
        return searchBST(root->left,val);
    }
};

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^4]的范围内。 * -10^8 <= Node.val <= 10^8 * 所有值 Node.val 是 独一无二 的。 * -10^8 <= val <= 10^8 * 保证 val 在原始BST中不存在。   思路： valleft=返回结果， val>root就继续在右子树查找。当遍历到空结点时直接创建并返回。

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root==nullptr){
            return new TreeNode(val);
        }
        if(root->val<val){
            root->right=insertIntoBST(root->right,val);
        }
        if(root->val>val){
            root->left=insertIntoBST(root->left,val);
        }
        return root;
    }
};

Leetcode 450. 删除二叉搜索树中的节点（中等）

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key * 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。 * * 一般来说，删除节点可分为两个步骤：   * 首先找到需要删除的节点； * 如果找到了，删除它。   * 示例 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^4]. * -10^5 <= Node.val <= 10^5 * 节点值唯一 * root 是合法的二叉搜索树 * -10^5 <= key <= 10^5   * 进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。   思路： 查找方式如上。当查找到node时，有以下三种情况： node无子节点：直接返回null，即直接删除 node只有左结点或右结点：返回左子节点或右子节点 node有左右结点：在右子树中找到最小值，替换到node，然后删除右子树中的这个最小节点  

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root==nullptr) return root;
        if(root->val==key){
            if(root->left==nullptr&&root->right==nullptr)
                return nullptr;
            if(root->left==nullptr){
                return root->right;
            }
            if(root->right==nullptr){
                return root->left;
            }
            TreeNode* min=getMin(root->right);
            root->val=min->val;
            root->right=deleteNode(root->right,min->val);

        }else if(root->val<key){
            root->right=deleteNode(root->right,key);
        } else{
            root->left=deleteNode(root->left,key);
        }
        return root;
    }
    TreeNode* getMin(TreeNode* root){
        while(root->left!=nullptr){
            root=root->left;
        }
        return root;
    }
};