第一章：手把手带你刷二叉搜索树-第二期

labuladong手把手带你刷二叉搜索树-第二期

实现 Binary Search Tree （BST）的基础操作：判断 BST 的合法性、增、删、查。

98. 验证二叉搜索树

方法1：利用携带的最大最小值进行判断

• root 需要做的不只是和左右子节点比较，而是要和整个左子树和右子树所有节点比较
• 使用辅助函数，增加函数参数列表，在参数中携带额外信息（当前节点需要比较的最小值和最大值）
  • 辅助递归函数的含义：给定一个最小值和一个最大值，判断它是否为合法的二叉搜索树
  • 相当于前序遍历。根节点需要判断它是否在最大值最小值的范围内，若不在，则返回false。若在，则调整左右子树的比较范围，并返回左右子树相与之后的结果。
  • 初始时刻，直接赋予最小值-float("inf")、最大值float("inf")。对于根节点，它和无穷小无穷大进行比较，显然是合法的，然后再考虑左右子树

了解了递归函数后，时刻明白递归函数的含义以及它的功能，不要跳进递归函数中

在递归的过程中修改最值（自顶向下的过程中，根节点先与最小值-float("inf") 和最大值float("inf") 比较，满足条件。然后左子树与最小值-float("inf") 和最大值（根节点值）比较。右子树同理。）在递归时，比较的最小值从-float("inf") 逐渐增大，最大值从float("inf") 逐渐减小）

以该不合法的二叉搜索树树为例：
- 遍历到15 时，15与 [10, float("inf")] 比较，结果是True（此时最小值为10）
- 对于15的左子树，它的比较范围变成了[10,15]，但现在是6，结果为False

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def valid(root,mi,ma):
            if root==None: return True
            if root.val<=mi: return False
            if root.val>=ma: return False
            return valid(root.left, mi , root.val) and valid(root.right, root.val, ma)
        return valid(root, -float("inf"), float("inf"))

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    bool valid(TreeNode *root, long mi, long ma) {
        if (root == nullptr)
            return true;
        if (root->val >= ma)
            return false;
        if (root->val <= mi)
            return false;
        return valid(root->left, mi, root->val) && valid(root->right, root->val, ma);

    }

    bool isValidBST(TreeNode *root) {
        return valid(root, LONG_MIN, LONG_MAX);
    }
};

方法2：中序遍历二叉搜索树后，判断其是否为没有重复元素的递增数组

• 最后的return nodes == sorted(set(nodes)), 要先set，再 sorted，这样返回的是列表形式，即判断列表是否等于列表（若先sorted，再set，返回的是一个集合，即判断列表是否等于集合，出现错误） 。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        nodes=[]
        def inOrder(root): # 中序遍历后，判断其是否递增
            if not root: return True
            inOrder(root.left)
            nodes.append(root.val)
            inOrder(root.right)
            return nodes

        inOrder(root)
        return nodes == sorted(set(nodes))

class Solution {
public:
//    中序遍历，并将结果保存在vec中
    vector<int>vec;
    vector<int> inOrder(TreeNode *root){
        if (root==nullptr)
            return vec;
        inOrder(root->left);
        vec.push_back(root->val);
        inOrder(root->right);
        return vec;
    }

    bool isValidBST(TreeNode *root) {
//        调用中序遍历函数，并将结果复制到vec1中
        inOrder(root);
        vector<int>vec1(vec);        
//        对vec去重并排序
        set<int>s(vec.begin(),vec.end());
        vec.assign(s.begin(),s.end());
        sort(vec.begin(),vec.end());
//        判断去重排序后的结果是否与原结果一致
        return vec1==vec;
    }
};

• P.S. C++给vector去重并排序

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    vector<int> vec{1, 2, 3, 4, 5, 4, 3, 2, 1};
////    给vector去重并排序
////    方法1：用set去重，sort排序
//    set<int>s(vec.begin(),vec.end());
//    vec.assign(s.begin(),s.end());
//    sort(vec.begin(),vec.end());

////    方法2：用sort函数排序，然后用unique函数
////    unique() 函数将重复的元素放到 vector 的尾部，然后返回指向第一个重复元素的迭代器,
////    再用 erase() 函数擦除从这个元素到最后元素的所有的元素
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    for (auto &v:vec) {
        cout << v << endl;
    }
}

方法3：递归函数

• 明确递归函数的含义：判断以root为根的树是否为合法的二叉搜索树。因为中序遍历时是升序排列，所以在遍历过程判断前一个数是否比当前数小；判断后，把前一个数更新为当前数，用于后续继续判断

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* pre=nullptr; // 初始的前一个节点先赋值nullptr
    bool isValidBST(TreeNode* root) {
        if (root==nullptr) return true; // 递归结束的条件
        // 中序遍历：左。判断左子树是否合法
        if (!isValidBST(root->left)) return false; 
        // 中序遍历：中。如果前一个数比当前节点数大，则不合法
        if (pre!=nullptr && pre->val>=root->val) return false;
        pre=root; // 如果前一个数小于当前节点数，则当前节点变为pre节点，用于后续的右子树比较
        return isValidBST(root->right); // 中序遍历：右
    }
};

700. 二叉搜索树中的搜索

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        # 递归结束的条件
        if not root: return None
        # 找到目标，做点什么
        if root.val==val: return root
        # 类似二分搜索思想
        if root.val>val:
            return seatchBST(self,root.left,val)
        if root.val<val:
            return searchBST(self,root.right,val)

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

对数据结构的操作无非遍历 + 访问，遍历就是“找”，访问就是“改”。具体到这个问题，插入一个数，就是先找到插入位置，然后进行插入操作。

上一个问题，我们总结了 BST 中的遍历框架，就是“找”的问题。直接套框架，加上“改”的操作即可。一旦涉及“改”，函数就要返回 TreeNode 类型，并且对递归调用的返回值进行接收。

• 递归函数的含义：插入数据，并返回根节点
• 相当于前序遍历。当前的根需要做的事情：找到空余根节点，把这个数据插入，然后返回root。如果这次没有空余的节点，则在左右子树中插入，然后返回根节点

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def insertIntoBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        # 找到空位置（可行的空位置可能不止一处），插入新节点        
        if not root:
            root=TreeNode(val)
            return root
        # 已经存在了，直接返回
        if (root.val==val):            
            return root
        # 如果val大，插到右子树，反之插到左子树
        if val>root.val:
            root.right=self.insertIntoBST(root.right,val)
        elif val< root.val:
            root.left=self.insertIntoBST(root.left,val)
        return root

////Definition for a binary tree node.
//struct TreeNode {
//    int val;
//    TreeNode *left;
//    TreeNode *right;
//    TreeNode() : val(0), left(nullptr), right(nullptr) {}
//    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
//};
class Solution {
public:
    TreeNode *insertIntoBST(TreeNode *root, int val) {
        if (root == nullptr)
            return new TreeNode(val, nullptr, nullptr);
        // if (root->val == val)  // 不要这个也可以，因为题目保证了数据不重复
        //     return root;
        if (val > root->val)
            root->right = insertIntoBST(root->right, val);
        else if (val < root->val)
            root->left = insertIntoBST(root->left, val);
        return root;
    }
};

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

• 情况1：若当前的叶子节点就是要删除的，则直接删除
• 情况2：若要删除的节点对应的左右孩子有一个为空，一个不为空，则让不为空的子孩子代替当前节点
• 情况3：若要删除的节点的左右孩子都不为空
  • 因为这是二叉搜索树，则左子树的所有元素都比右子树的小。所以可以把左子树拼接到右子树最左边的节点处，然后用右子树代替当前节点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
//    找到当前节点的最左节点
    TreeNode *getMin(TreeNode *root) {
        while (root->left != nullptr) {
            root = root->left;
        }
        return root;
    }

    TreeNode *deleteNode(TreeNode *root, int key) {
        if (root == nullptr) return root; // 递归结束的条件
//      当前元素就是要删除的元素
        if (root->val == key) {
            // 处理没有子节点或者只有一个子节点的情况
            if (root->left == nullptr) return root->right;
            if (root->right == nullptr) return root->left;
            // 处理两个子节点都不为空的情况
            TreeNode *minR = getMin(root->right);
            minR->left = root->left;
            root = root->right;
        } else if (key > root->val) {
            root->right = deleteNode(root->right, key);     // 去右子树删除
        } else {
            root->left = deleteNode(root->left, key); // 去左子树删除
        }
        return root;  // 处理完子树后，返回最终的root
    }
};

在处理情况3时，也可以

• （1）让右子树的最小元素节点的值代替当前节点的值（或让左子树的最大元素代替当前节点）
• （2）右子树的最小元素节点一定在它的左节点，于是用while循环找到最小元素节点
• （3）然后把这个最小元素节点的值赋值给当前root，转而去删除右子树中的这个最小元素节点

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def deleteNode(self, root, key):
        """
        :type root: TreeNode
        :type key: int
        :rtype: TreeNode
        """


        # 若无根节点，直接返回；（递归结束的条件）
        if not root:return None
        # 若找到目标值
        if root.val==key:
            # 处理无子节点/只有一个子节点的情况
            if root.left==None: return root.right
            if root.right==None: return root.left

            # 找到右子树的最左（小）节点，并替换
            minNode=self.getMin(root.right)
            root.val=minNode.val
            # 转而删除最小节点
            root.right=self.deleteNode(root.right,minNode.val)
        # 二叉搜索树
        elif root.val>key:
            root.left=self.deleteNode(root.left,key)
        else:
            root.right=self.deleteNode(root.right,key)
        return root

    def getMin(self,root): # 最小值一定在左叶子节点处
        while root.left!=None:
            root=root.left
        return root

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* getMin(TreeNode* root){
        if (root==nullptr) return root;
        while (root->left!=nullptr){
            root = root->left;
        }
        return root;
    }
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root== nullptr) return root; // 递归结束的条件
//      当前元素就是要删除的元素
        if (root->val==key){
            // 处理没有子节点或者只有一个子节点的情况
            if (root->left == nullptr) return root->right;
            if (root->right == nullptr) return root->left;
            // 处理两个子节点都不为空的情况

            TreeNode *minVal = getMin(root->right);
            root->val = minVal->val;
            root->right = deleteNode(root->right, minVal->val);
        } else if (root->val<key){ // 小于目标值，则在右子树中找，并返回右子树
            root->right = deleteNode(root->right,key);
        }else{ // 大于目标值，在左子树中找，并返回左子树
            root->left=deleteNode(root->left,key);
        }
        return root;  // 处理完子树后，返回最终的root
    }
};