235. 二叉搜索树的最近公共祖先
题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
算法思想：利用二叉搜索树的特性。左子树的值都比根节点小，右子树的值都比根节点大。递归遍历。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL)
return NULL;
if(root->val > p->val&& root->val>q->val)
{
TreeNode* left = lowestCommonAncestor(root->left, p, q);
return left;
}
else if(root->val < p->val&& root->val < q->val)
{
TreeNode* right = lowestCommonAncestor(root->right, p, q);
return right;
}
else if(root->val > p->val && root->val < q->val)
return root;
return root;
}
};
701. 二叉搜索树中的插入操作
题目链接：
算法思想：
递归终止条件，当遇到空节点的时候，就说明找到位置了，新建立一个结果，并返回，然后让上一轮递归的根节点的左孩子或者右孩子接住它。
代码：
https://leetcode.cn/problems/insert-into-a-binary-search-tree/
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root==NULL)
{
TreeNode* node = new TreeNode(val);
return node;
}
if(root->val > val)
{
root->left = insertIntoBST(root->left, val);
}
else if(root->val < val)
{
root->right = insertIntoBST(root->right, val);
}
return root;
}
};
450. 删除二叉搜索树中的节点
题目链接：https://leetcode.cn/problems/delete-node-in-a-bst/
算法思想：递归终止条件分情况讨论。
1.如果未找到，则返回空
2.如果找到了，且左右孩子未空，则返回空
3.如果找到了，左孩子不为空，右孩子未空，则返回左孩子
4.如果找到了，左孩子为空，右孩子不为空，则返回右孩子
5.如果找到了，左右孩子都不为空，则将左孩子放到右子树的最左子节点上。
代码：
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
//
if(root==NULL)
{
return root;
}
//如果找到了要删除的节点
if(root->val == key)
{
if(root->left ==NULL && root->right == NULL)
return NULL;
else if(root->right==NULL)
{
return root->left;
}
else if(root->left==NULL)
{
return root->right;
}
else
{
TreeNode *cur = root->right;
while(cur->left!=NULL)
{
cur = cur->left;
}
cur->left = root->left;
return root->right;
}
}
if(root->val > key)
root->left = deleteNode(root->left, key);
else if(root->val < key)
root->right = deleteNode(root->right, key);
return root;
}
};
