235. 二叉搜索树的最近公共祖先
思路：
第236是针对普通二叉树求最近公共祖先，这道题是针对二叉搜索树。二叉搜索树是有顺序的树，从左到右各个节点的值依次增大，利用这一个特性就可以避免遍历所以的节点。如果父节点的值大于p、q，则在左子树搜索，如果父节点的值小于p、q，则到右子树搜索，如果父节点位于p、q之间，则该节点将会是最近的共同祖先。
代码：
(递归法)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* gettree(TreeNode* pointer, TreeNode* p, TreeNode* q)
{
if(pointer==NULL)return pointer;
if(pointer->val>p->val && pointer->val>q->val)
{
TreeNode* lefttree=gettree(pointer->left,p,q);
if(lefttree!=NULL) return lefttree;
}
if(pointer->val<p->val && pointer->val<q->val)
{
TreeNode* righttree=gettree(pointer->right,p,q);
if(righttree!=NULL) return righttree;
}
return pointer;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return gettree(root,p,q);
}
};
（迭代法）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while(root!=NULL)
{
if(root->val>p->val &&root->val>q->val)
{
root=root->left;
}
else if(root->val <p->val &&root->val <q->val)
{
root=root->right;
}else{
return root;
}
}
return NULL;
}
};
701. 二叉搜索树中的插入操作
思路：
因为插入的方式有多种，其中一种可以将插入的节点放在叶子节点上，这样的话只需要遍历到叶子节点然后根据值的大小插入即可。需要注意的是，在写递归结束条件时，因为此时的cur指向了NULL，对其无法进行操作，所以一定要有一个节点保存上一个节点。
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* temp;//记录上一个节点
void insert(TreeNode* cur, int val)
{
if(cur==NULL)
{
TreeNode* node=new TreeNode(val);
if(temp->val>val)
{
temp->left=node;
}else
{
temp->right=node;
}
return;
}
temp=cur;
if(cur->val>val)
{
insert(cur->left,val);
}
if(cur->val<val)
{
insert(cur->right,val);
}
return;
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
temp=new TreeNode(0);
if(root==NULL)
{
return new TreeNode(val);
}
insert(root,val);
return root;
}
};
450. 删除二叉搜索树中的节点
思路：
针对二叉树的节点有不同的情况，删除二叉树节点有以下五种情况：
（1）没找到删除的节点，返回原二叉树即可
（2）删除叶子节点，直接让其父节点指向空即可
（3）删除的节点的左孩子为空，右孩子不为空。直接让其父节点的父节点直接指向该节点即可。
（4）删除的节点左孩子不为空，右孩子为空。直接让其父节点的父节点直接指向该节点即可。
（5）删除的节点其左右孩子均不为空。选择其某一边的节点来继承该节点的位置，例如让右子树来继承该节点的位置，让该节点父节点的父节点直接直接指向该节点，然后让该节点的左子树挂载到右子树最左边的叶子节点上即可。
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
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)
{
delete root;
return NULL;
}
else if(root->left!=NULL && root->right==NULL)
{
auto leftnode=root->left;
delete root;
return leftnode;
}
else if(root->right!=NULL &&root->left==NULL)
{
auto rightnode=root->right;
delete root;
return rightnode;
}
else{
TreeNode* cur=root->right;
while(cur->left!=NULL)
{
cur=cur->left;
}
cur->left=root->left;
TreeNode* rightnode = root->right;
delete root;
return rightnode;
}
}
if(root->val>key) root->left=deleteNode(root->left,key);
if(root->val<key)root->right=deleteNode(root->right,key);
return root;
}
};
