本文主要是介绍代码随想录算法训练营Day22|235. 二叉搜索树的最近公共祖先 ，701.二叉搜索树中的插入操作 ，450.删除二叉搜索树中的节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
235. 二叉搜索树的最近公共祖先：代码随想录
这道题目的意思和前面的二叉树的最近公共祖先一样，只不过是换成了二叉搜索树，我采用的方法还是和普通二叉树一样，利用回溯的方法，来看具体代码的实现
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==NULL) return NULL;if(root==p || root==q) return root;TreeNode* leftTree=lowestCommonAncestor(root->left,p,q);TreeNode* rightTree=lowestCommonAncestor(root->right,p,q);if(leftTree!=NULL && rightTree!=NULL) return root;if(leftTree==NULL && rightTree!=NULL) return rightTree;if(leftTree!=NULL && rightTree==NULL) return leftTree;return NULL;}
};当结点为空时，说明没有找到目标的结点，返回空，当找到时，就返回当前节点，后序遍历，如果左右孩子都不为空，说明该结点就是祖先，返回即可。下面来看卡哥的代码
class Solution {
private:TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {if (cur == NULL) return cur;// 中if (cur->val > p->val && cur->val > q->val) { // 左TreeNode* left = traversal(cur->left, p, q);if (left != NULL) {return left;}}if (cur->val < p->val && cur->val < q->val) { // 右TreeNode* right = traversal(cur->right, p, q);if (right != NULL) {return right;}}return cur;}
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return traversal(root, p, q);}
};当结点为空时，返回空，当两个结点的值都小于时，往左孩子搜索，反之往右孩子搜索，其他情况就说明在该节点的左右两边。说明该节点就是祖先，返回即可
701.二叉搜索树中的插入操作：代码随想录
这道题就是让你在二叉搜索树中插入结点，很简单直接看代码
class Solution {
public:TreeNode* insertIntoBST(TreeNode* &root, int val) {if(root==NULL){root= new TreeNode(val);}else if(val<root->val){TreeNode* leftTree=insertIntoBST(root->left,val);}else if(val>root->val){TreeNode* rightTree=insertIntoBST(root->right,val);}return root;}
};当到叶子结点时，就新建一个节点就可以了。
450.删除二叉搜索树中的节点：代码随想录
这道题就是让你删除一个节点，并且保证删除过后仍然是一个而二叉搜索树，这里要分情况讨论，先来看代码，这里我采用的方法是链接左子树的结点，而卡哥是连接右子树的结点，
class Solution {
public:TreeNode* deleteNode(TreeNode* &root, int key) {return Delete(root,key);}TreeNode* Delete(TreeNode* &root, int val){if(root==NULL) return NULL;if(root->val==val){if(root->left==NULL && root->right==NULL){return NULL;}if(root->left==NULL && root->right!=NULL){//TreeNode* p=root;return root->right;}if(root->left!=NULL && root->right==NULL){//TreeNode* p=root;return root->left;// delete p;}if(root->left!=NULL && root->right!=NULL){TreeNode* p=root->left;while(p->right!=NULL){p=p->right;}if(p==root->left){p->right=root->right;return root->left;}else{p->right=root->right;return root->left;}}}if(root->val>val){root->left = Delete(root->left,val);}if(root->val<val){root->right = Delete(root->right,val);}return root;}
};首先当结点为空时，就直接返回空，如果该节点就是要删除的结点，并且他的左右孩子为空，那就直接返回空，注意这里的函数是有返回值的，会有上一层的结点的左右孩子来接收，如果是左孩子或者右孩子为空的情况，那就返回不是空的那个就可以了，如果是都不为空，那么就看左子树的离要删除的结点的数值最近的那个就是root结点的左孩子一直向右遍历的结点，让该节点的右孩子等于root的右孩子，然后返回root的left即可。
这篇关于代码随想录算法训练营Day22|235. 二叉搜索树的最近公共祖先 ，701.二叉搜索树中的插入操作 ，450.删除二叉搜索树中的节点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
