代码随想录算法训练营第二十二天 | LeetCode235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

---

一、235. 二叉搜索树的最近公共祖先

解题代码C++：

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root->val > p->val && root->val > q->val) {return lowestCommonAncestor(root->left, p, q);} else if (root->val < p->val && root->val < q->val) {return lowestCommonAncestor(root->right, p, q);} else return root;}
};

题目链接/文章讲解/视频讲解：
https://programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html

---

---

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

解题代码C++：

class Solution {
private:TreeNode* parent;void traversal(TreeNode* cur, int val) {if (cur == NULL) {TreeNode* node = new TreeNode(val);if (val > parent->val) parent->right = node;else parent->left = node;return;}parent = cur;if (cur->val > val) traversal(cur->left, val);if (cur->val < val) traversal(cur->right, val);return;}public:TreeNode* insertIntoBST(TreeNode* root, int val) {parent = new TreeNode(0);if (root == NULL) {root = new TreeNode(val);}traversal(root, val);return root;}
};

题目链接/文章讲解/视频讲解：
https://programmercarl.com/0701.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%8F%92%E5%85%A5%E6%93%8D%E4%BD%9C.html

---

---

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

解题代码C++：

class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return root;if (root->val == key) {if (root->right == nullptr) { // 这里第二次操作目标值：最终删除的作用return root->left;}TreeNode *cur = root->right;while (cur->left) {cur = cur->left;}swap(root->val, cur->val); // 这里第一次操作目标值：交换目标值其右子树最左面节点。}root->left = deleteNode(root->left, key);root->right = deleteNode(root->right, key);return root;}
};

题目链接/文章讲解/视频讲解：
https://programmercarl.com/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html