2 - 二叉搜索树BST
二叉搜索树(Binary Search Tree, BST)是特殊的二叉树,它满足如下性质:
- 左小右大:对于BST的每一个节点,它左子树节点的值都小于根节点的值,右子树节点的值都大于根节点的值。
- 递归定义:对于BST的每一个节点,它的左子树和右子树也都是BST。
- 中序升序:BST的中序遍历结果是升序的。
直接基于BST的数据结构有AVL树、红黑树等,拥有自平衡性质;还有B+树,线段树等结构都是基于BST的思想来设计的。因此学好BST也很重要。
中序升序
230. 二叉搜索树中第K小的元素 - 力扣(LeetCode)
可以利用中序遍历来找:
int ans = 0;
int rank = 0;
void traverse(TreeNode* root, int k)
{
if (root)
{
traverse(root->left, k);
rank++;
if (rank == k)
{
ans = root->val;
return;
}
traverse(root->right, k);
}
}
int kthSmallest(TreeNode* root, int k) {
traverse(root, k);
return ans;
}
如果可以自定义BST节点,那么可以新增一个size
成员,它表示以自己为根的BST节点数。然后配合左子树根节点和右子树根节点的size
,就能确认当前的排名。确认排名后,便可进行“剪枝”操作,往目标排名处搜索。
538. 把二叉搜索树转换为累加树 - 力扣(LeetCode)
我们可以通过倒序的中序遍历(右中左)的方式来解决这道题,只需这样遍历一次,维护每个节点的累加和就好了:
int sum = 0;
void traverse(TreeNode* root)
{
if (root)
{
traverse(root->right);
sum += root->val;
root->val = sum;
traverse(root->left);
}
}
TreeNode* convertBST(TreeNode* root) {
traverse(root);
return root;
}
类似题目:
- 1038. 从二叉搜索树到更大和树 - 力扣(LeetCode)
增删改查
利用BST左小右大的特性,可以快速查找到目标节点。BST的遍历框架如下:
void traverseBST(TreeNode* root, int target)
{
if (root)
{
if (root->val == target)
{
// 找到了, 做点什么
}
else if (root->val > target)
traverseBST(root->left, target);
else
traverseBST(root->right, target);
}
}
判断BST合法性
98. 验证二叉搜索树 - 力扣(LeetCode)
有时候要根据BST“左小右大”的特性来判断BST合法性,可以这样写:
bool traverse(TreeNode* root, long minVal, long maxVal)
{
if (root)
{
if (root->val <= minVal) return false;
if (root->val >= maxVal) return false;
return traverse(root->left, minVal, root->val) && traverse(root->right, root->val, maxVal);
}
return true;
}
bool isValidBST(TreeNode* root) {
return traverse(root, numeric_limits<long>::lowest(), numeric_limits<long>::max());
}
这里由于树节点是int
类型,最大值最小值使用long
。
插入一个数
可以使用BST的遍历框架,找到符合条件的空节点位置,然后在这里插入:
TreeNode* insertBST(TreeNode* root, int val)
{
// 找到空节点位置
if (root == nullptr)
return new TreeNode(val);
else
{
if (root->val > val)
root->left = insertBST(root->left, val);
else if (root->val < val)
root->right = insertBST(root->right, val);
else
return root;
}
}
删除一个数
要删除一个数,首先得先找到它,用traverseBST()
框架找到这个节点。找到后该如何删除呢,得分情况讨论:
- 要删除的节点是叶子节点,那么它可以被直接删除。
- 要删除的节点只有一个孩子节点,那么让该孩子节点接替自己的位置。
- 要删除的节点有两个孩子节点,有两种选择:找到左子树中最大的节点,然后替换自己;找到右子树中最小的节点,然后替换自己。
代码如下:
TreeNode* deleteBST(TreeNode* root, int target)
{
if (root == nullptr) return nullptr;
if (root->val == target)
{
// 情况1和2
if (root->left == nullptr)
return root->right;
if (root->right == nullptr)
return root->left;
// 情况3: 这里找右子树最小节点, 然后替换
TreeNode* minNode = root->right;
while (minNode->left)
minNode = minNode->left;
// 删除右子树最小节点
root->right = deleteBST(root->right, minNode->val);
// 然后用最小节点替换root节点
minNode->left = root->left;
minNode->right = root->right;
root = minNode;
}
else if (root->val > target)
root->left = deleteBST(root->left, target);
else if (root->val < target)
root->right = deleteBST(root->right, target);
return root;
}