代码随想录算法训练营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);}
};

当结点为空时，返回空，当两个结点的值都小于时，往左孩子搜索，反之往右孩子搜索，其他情况就说明在该节点的左右两边。说明该节点就是祖先，返回即可

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;}
};

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;}
};