二叉搜索树（BST）合集_bst性质

目录

一、BST定义和性质

二、二叉搜索树中第K小的元素

三、把二叉搜索树转换为累加树

四、合法二叉搜索树

五、二叉搜索树中的搜索

六、二叉搜索树中的插入操作

七、在 BST 中删除一个数

八、不同的二叉搜索树

 九、不同的二叉搜索树 II

---

一、BST定义和性质

定义：BST是一棵空树，或者具有以下性质的二叉树：

性质：

• 若它的左子树不空，则左子树的所有节点值都小于根节点的值
• 若它的右子树不空，则右子树的所有节点值都大于根节点的值
• 左子树和右子树都是二叉搜索树

备注：BST中序遍历是升序序列

根据以上性质，下面介绍相关BST题型

二、二叉搜索树中第K小的元素

题目：给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：

 
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

分析：

• 根据BST中序遍历为升序序列，则该题进行中序遍历，遍历到第K个节点即可

示例代码：

int nRet = 0;
int nIndex = 0;
void help(TreeNode* root,int k)
{
    if (root == nullptr)
    {
        return ;
    }
 
    if (root->left != nullptr)
    {
        help(root->left,k);
    }
    nIndex++;
    if (k == nIndex)
    {
        nRet = root->val;
        return ;
    }
    // vecNum.push_back(root->val);
    if (root->right != nullptr)
    {
        help(root->right,k);
    }
}
int kthSmallest(TreeNode* root, int k) {
    help(root,k);
    return nRet;
}

三、把二叉搜索树转换为累加树

题目：给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

示例 1：

 输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：

输入：root = [0,null,1]
输出：[1,null,1]
示例 3：

输入：root = [1,0,2]
输出：[3,3,2]
示例 4：

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

分析：

• 虽然BST中序遍历是升序序列，但是当前节点的父节点也比本身大，并且获取不到父节点
• 所以我们还是根据中序遍历的性质，先遍历右子树，在遍历左子树，成为降序序列

示例代码：

TreeNode* convertBST(TreeNode* root) {
    help(root);
    return root;
}
int nSum = 0;
void help(TreeNode* root)
{
    if (root == nullptr)
    {
        return;
    }
    help(root->right);
    nSum += root->val;
    root->val = nSum;
    help(root->left);
}

四、合法二叉搜索树

题目：实现一个函数，检查一棵二叉树是否为二叉搜索树。

示例 1:
输入:
    2
   / \
  1   3
输出: true
示例 2:
输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 

分析：

• 根据BST左子树大于右子树性质，我们很容易写出如下代码：

boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    if (root.left != null && root.val <= root.left.val)
        return false;
    if (root.right != null && root.val >= root.right.val)
        return false;
    return isValidBST(root.left)
        && isValidBST(root.right);
}

但是看如图：

符合上面的代码，缺不是一棵二叉搜索树 ，因为我们只检查了该节点的左右子节点，但是BST性质是左右子树。

• 我们可以增加两个变量，存储最大值和最小值节点

示例代码：

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

五、二叉搜索树中的搜索

题目：给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

例如，

给定二叉搜索树:

        4
       / \
      2   7
     / \
    1   3

和值: 2
你应该返回如下子树:

      2     
     / \   
    1   3

分析：

• 根据BST性质，如果root->val == val则返回root
• 如果root->val > val，则遍历左子树
• 如果root->val < val，则遍历右子树

示例代码：

TreeNode* searchBST(TreeNode* root, int val) {
    return help(root,val);
}
TreeNode * help(TreeNode* root, int val)
{
    if (root == nullptr)
    {
        return nullptr;
    }
    if (root->val == val)
    {
        return root;
    }
    else if (root->val > val)
    {
        return help(root->left,val);
    }
    else if (root->val < val)
    {
        return help(root->right,val);
    }
    return nullptr;
}

六、二叉搜索树中的插入操作

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

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

示例 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]

分析：

 

示例代码：

TreeNode* insertIntoBST(TreeNode* root, int val) {
    return help(root,val);
}
TreeNode * help(TreeNode* root, int val)
{
    if (root == nullptr)
    {
        root = new TreeNode(val);
    }
    if (root->val > val)
    {
        root->left = help(root->left,val);
    }
    else if(root->val < val)
    {
        root->right = help(root->right,val);
    }
    return root;
}

七、在 BST 中删除一个数

题目：给定一个BST和一个目标数，将该节点删除。

例如：

 分析：

• 根据BST性质，很容易找到要删除的节点A
• 删除节点A分如下三种情况讨论

1. A的左右节点都为空，如题示例，则：
       if (root.left == null && root.right == null)                                                                            return null;
2. A只有一个非空子节点，那么要让这个孩子节点接替自己位置，如图：if (root.left == null) return root.right;
   if (root.right == null) return root.left;
3. A有两个非空子节点，为了不破坏BST性质，A必须找到左子树中最大的那个节点，或者右子树最小的那个节点接替自己位置，如图：

      if (root.left != null && root.right != null) {//以找右子树最小值为例
              // 找到右子树的最小节点
             TreeNode minNode = getMin(root.right);
             // 把 root 改成 minNode
             root.val = minNode.val;
             // 转而去删除 minNode
             root.right = deleteNode(root.right, minNode.val);
        }

 示例代码：

TreeNode* deleteNode(TreeNode *root, int key) {
    if (root == nullptr)
    {
        return nullptr;
    }
    if (root->val == key) {
        // 这两个 if 把情况 1 和 2 都正确处理了
        if (root->left == nullptr)
        {
            return root->right;
        }
        if (root->right == nullptr)
        {
            return root->left;
        }
        // 处理情况 3
        TreeNode* minNode = getMin(root->right);
        root->val = minNode->val;
        root->right = deleteNode(root->right, minNode->val);
    }
    else if (root->val > key)
    {
        root->left = deleteNode(root->left, key);
    }
    else if (root->val < key)
    {
        root->right = deleteNode(root->right, key);
    }
    return root;
}
 
TreeNode* getMin(TreeNode* node) {
    // BST 最左边的就是最小的
    while (node->left != nullptr)
    {
        node = node->left;
    }
    return node;
}

八、不同的二叉搜索树

题目：给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5
示例 2：

输入：n = 1
输出：1

分析：

• 根节点可以有n种选择
• 比如n = 5，选择3为根节点，则{1,2}就是左子树组合，{4,5}就是右子树组合
• 左右子树组合乘积就是以3为根节点的BST种数

示例代码：

//备忘录消除一下重复子项
int numTrees(int n) {
    vector<vector<int>> memo(n + 1, vector<int>(n + 1,0));
    return help(1,n,memo);
}
int help(int nLow, int nHeight,vector<vector<int>> &memo)
{
    if (nLow > nHeight)
    {
        return 1;
    }
    if (memo[nLow][nHeight] != 0)
    {
        return memo[nLow][nHeight];
    }
    int ret = 0;
    for (int i = nLow; i <= nHeight; i++)
    {
        //以i为根节点
        int nLeft = help(nLow, i - 1,memo);
        int nRight = help(i + 1, nHeight,memo);
        ret += nLeft * nRight;
    }
    memo[nLow][nHeight] = ret;
    return ret;
}

 九、不同的二叉搜索树 II

题目：给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

示例 1：

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
示例 2：

输入：n = 1
输出：[[1]]

分析：

• 根据例题8的解析，可知道BST总数
• 只是需要保存一下每个节点信息

示例代码：

vector<TreeNode*> generateTrees(int n) {
    return help(1,n);
}
vector<TreeNode *> help(int nLow, int nHeight)
{
    vector<TreeNode *> ret;
    if (nLow > nHeight)
    {
        ret.push_back(nullptr);
        return ret;
    }
    for (int i = nLow; i <= nHeight; i++)
    {
        vector<TreeNode *> left = help(nLow, i - 1);
        vector<TreeNode *> right = help(i + 1, nHeight);
 
        for (auto & leftNode : left)
        {
            for (auto &rightNode : right)
            {
                TreeNode *root = new TreeNode(i);
                root->left = leftNode;
                root->right = rightNode;
                ret.push_back(root);
            }
        }
    }
    return ret;
}