- 235 二叉搜索树的最近公共祖先
- 701 二叉搜索树中的插入操作
- 450 删除二叉搜索树中的节点
235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
方法一： 递归写法
如果 cur->val 小于 p->val，同时 cur->val 小于 q->val，那么就应该向右遍历（目标区间在右子树）。反之，向左遍历。
剩下的情况，就是cur节点在区间，那么cur就是最近公共祖先了，直接返回cur
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//递归三要素: 确定终止条件
if(root == null) return root;
//递归三要素： 单层逻辑
if(root.val > p.val && root.val > q.val){ //root值大于p,q，向左寻找
return lowestCommonAncestor(root.left, p, q);
}else if(p.val > root.val && q.val > root.val){ //root值小于p,q，向右寻找
return lowestCommonAncestor(root.right, p, q);
}else{//root 位于p,q之间,root就是lowest Common Ancestor
return root;
}
}
}
方法二 . 迭代
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return root;
while(true){
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{
break;
}
}
return root;
}
}
时间复杂度： O(n)
空间复杂度： O(1)
701. 二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。
思路： 只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。
递归：
- 确定终止条件
终止条件就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回。 - 确定单层递归的逻辑
根据BST特性，如果root.val < val, 说明val应该出现在root右侧，向右子树寻找； 反之向左寻找
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null) return new TreeNode(val);
if(root.val < val){
root.right = insertIntoBST(root.right, val);
}else{
root.left = insertIntoBST(root.left, val);
}
return root;
}
}
迭代：
在迭代法遍历的过程中，需要记录一下当前遍历的节点的父节点，这样才能做插入节点的操作
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null) return new TreeNode(val);
TreeNode cur = root;
TreeNode pre = root; //当前遍历的节点的父节点
while(cur != null){
pre = cur;
if(cur.val > val){
cur = cur.left;
}else{
cur = cur.right;
}
}
if(pre.val > val){
pre.left = new TreeNode(val);
}else{
pre.right = new TreeNode(val);
}
return root;
}
}
时间复杂度：O(N)，其中 N 为树中节点的数目。最坏情况下，我们需要将值插入到树的最深的叶子结点上，而叶子节点最深为 O(N)。
空间复杂度：O(1)。我们只使用了常数大小的空间。
450. 删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。
删除节点的五种情况：
- 树中没有需要删除的节点
返回root - 要删除的节点是叶子节点
直接删除 - 要删除的节点左空右不空
父节点直接指向右孩子 - 要删除的节点右空左不空
父节点直接指向左孩子 - 要删除的节点左右均不为空
左孩子继位，原来的右子树成为左孩子的最右叶子的右孩子
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
//没有找到需要删除的节点
if(root == null) return null;
if(key > root.val){
// 去右子树删除
root.right = deleteNode(root.right, key);
}else if(key < root.val){
// 去左子树删除
root.left = deleteNode(root.left, key);
}else{
//key found
//要删除的节点是叶子节点
if (root.left == null && root.right == null) {
return null;
}
//要删除的节点左空右不空, 父节点直接指向右孩子
if(root.left == null) return root.right;
//要删除的节点右空左不空, 父节点直接指向左孩子
if(root.right == null) return root.left;
//左右都不为空，原来的右子树成为左孩子的最右叶子的右孩子，左孩子继位，
TreeNode cur = root.left;
while(cur.right != null){
cur = cur.right;
}
cur.right = root.right;
root = root.left; // 左孩子顶替被删除节点的位置，节点被删除
}
return root;
}
}
时间复杂度 O(n)
空间复杂度O(n)
