235. 二叉搜索树的最近公共祖先
思路：二叉搜索树首先考虑中序遍历。根据二叉搜索树的特性，如果p,q分别在中间节点的左右两边，该中间节点一定是最近公共祖先，如果在同一侧，则递归这一侧即可。
递归三部曲：
1、传入参数：根节点，p，q，返回节点。
2、终止条件：因为p,q一定存在，所以不会遍历到树的最底层，因此可以不写终止条件
3、递归逻辑：如果p,q均小于root的值，递归调用左子树；如果p,q均大于root的值，递归调用右子树。否则直接返回root。
代码如下：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(p.val<root.val && q.val<root.val) return lowestCommonAncestor(root.left,p,q);
else if(p.val>root.val && q.val>root.val) return lowestCommonAncestor(root.right,p,q);
else return root;
}
}
该题使用迭代也比较简单，和递归同样的逻辑。代码如下：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode node=root;
while(node!=null){
if(p.val<node.val && q.val<node.val) node=node.left;
else if(p.val>node.val && q.val>node.val) node=node.right;
else return node;
}
return null;
}
}
701.二叉搜索树中的插入操作
思路：中序遍历递归。如果要插入的值小于节点值，遍历左子树；反之右子树，当遍历到空值的时候将节点插入。
递归三步曲：
1、传入参数：根节点，要插入的值。
2、终止条件：如果树为空，直接返回插入的节点。
3、递归函数逻辑：如果要插入的值小于节点值，递归调用左子树，并将返回值赋给当前节点的左孩子；右子树亦然。
代码如下：
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null) return new TreeNode(val);
if(val<root.val){
root.left=insertIntoBST(root.left,val);
}else{
root.right=insertIntoBST(root.right,val);
}
return root;
}
}
迭代方法需要记录父节点，也比较简单。代码如下：
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null) return new TreeNode(val);
TreeNode pre=null;
TreeNode node=root;
while(node!=null){
pre=node;
if(val<node.val){
node=node.left;
}else{
node=node.right;
}
}
if(val>pre.val) pre.right=new TreeNode(val);
else pre.left=new TreeNode(val);
return root;
}
}
450.删除二叉搜索树中的节点
思路：中序遍历递归二叉搜索树，先找到目标值的节点，需要定义全局变量记录前一个节点，如果目标节点为前一个节点的左孩子且左孩子的左孩子不是空，将前一个节点的左孩子指向目标节点的左孩子，目标节点的左孩子的右孩子为目标节点的右孩子，否则指向右孩子；如果目标节点为前一个节点的右孩子且右孩子的右孩子不是空，将前一个节点的右孩子指向目标节点的右孩子，目标节点的右孩子的左孩子为目标节点的左孩子，否则指向左孩子。递归主要用来找到目标节点。
递归三步曲：
1、传入参数：根节点和删除的目标值，返回值为树的某一个节点；
2、终止条件：如果节点为空，返回root；
3、递归函数逻辑：如果目标值小于节点值，递归左子树，返回值传给当前节点的左孩子；如果目标值大于节点值递归右子树，返回值传给当前节点的右孩子。如果目标值等于当前节点值，有五种删除节点的情况：
- 第一种情况：没找到删除的节点，遍历到空节点直接返回了
找到删除的节点 - 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
- 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
- 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
- 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
代码如下：
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root==null) return root;
if(key==root.val){
if(root.left==null){
return root.right;
}else if(root.right==null){
return root.left;
}else{
TreeNode cur=root.right;
while(cur.left!=null){
cur=cur.left;
}
cur.left=root.left;
return root.right;
}
}
if(key<root.val) root.left=deleteNode(root.left,key);
if(key>root.val) root.right=deleteNode(root.right,key);
return root;
}
}