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

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

利用二叉树特性，最近公共祖先，大于其中一个小于其中一个

代码：

class Solution {
public:  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//不需要终止判断，因为一定找的到// if(!root) return NULL;TreeNode* result=NULL;if(root->val>p->val&&root->val>q->val){result=lowestCommonAncestor(root->left,p,q);}else if(root->val<p->val&&root->val<q->val){result=lowestCommonAncestor(root->right,p,q);}elsereturn root;//找到后就开始不断返回，因为是if，else if，所有是有方向的搜索，找到后返回return result;}
};

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

可以插入在叶子节点

代码：

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);} if (root->val < val) {root->right = insertIntoBST(root->right, val);}//返回上一层return root;}
};

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

五种情况

代码：

class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if(!root) return nullptr;if(root->val==key){if(root->left==nullptr&&root->right==nullptr){delete root;return nullptr;}else if(root->left==nullptr&&root->right!=nullptr){TreeNode* temp=root->right;delete root;return temp;}else if(root->left!=nullptr&&root->right==nullptr){TreeNode* temp=root->left;delete root;return temp;}else{TreeNode* temp=root->right;while(temp->left!=nullptr){temp=temp->left;}temp->left=root->left;TreeNode* result=root->right;delete root;return result;}}if(key<root->val){root->left=deleteNode(root->left,key);}if(key>root->val){root->right=deleteNode(root->right,key);}return root;}
};