二叉树的第七天！
题目链接：235. 二叉搜索树的最近公共祖先
状态：看视频讲解后一次性AC
利用二叉搜索树的性质可以很容易的寻找p与q的公共祖先的位置。所以如果用递归的方法的话，就是递归三部曲：参数就是root， p， q三个节点，其中在每次递归时，root传入的都是当前层次的下一个节点，例如root.left或root.right。终止条件就是递归到root.val介于p.val与q.val之间。单层递归逻辑是如果root.val同时大于p.val和q.val，就向左节点递归；如果root.val同时小于p.val和q.val就向右节点递归。迭代法也是这个思路。本题关键在于为什么满足 root.val介于p.val与q.val之间 （这个条件） 的第一个节点就一定是最近公共祖先？这个这样理解：root的值介于p q 之间，那p, q 一定是一个在root的左子树，另一个在root的右子树中。所以无论往左或者往右再递归一层，都不再是另一个节点的祖先，（即错过另外一个）完整代码如下：
class Solution { // Java
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
return root;
}
}
复杂度分析：
时间复杂度：O(h). h为树高， 树高决定递归深度
空间复杂度：O(h). h为树高， 同上
题目链接：701. 二叉搜索树中的插入操作
状态：一次性AC
本题可能最难想的点就在于如何添加 或 在哪插入节点了，但是想清楚无论何种情况，都可以在叶子节点找到合适的位置添加元素，这题就很简单了。因为题目也没说是添加之后要变成平衡二叉树。
所以思路也很简单，根据数值的大小，利用二叉搜索树的性质，一直递归到底层然后添加节点。
所以递归的方法中，参数就是节点root和添加的数值val。递归结束的条件就是找到空节点。单层递归逻辑就是根据值的大小找寻正确的方向，值比当前节点的值大就往右边找，值比当前节点的值小就往左边找。完整代码如下：
class Solution { // Java
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 if(root.val > val){
root.left = insertIntoBST(root.left, val);
}
return root;
}
}
复杂度分析：
时间复杂度：O(h). h为树高， 树高决定递归深度
空间复杂度：O(h). h为树高， 同上
题目链接：450. 删除二叉搜索树中的节点
状态：看了教程，跟着代码敲，才AC。还得细细琢磨
本题难点在于删除节点会改变树的结构，因此得列举出每一种情况才好应对。教程里说一共是有五种情况：
- 没找到删除的节点，遍历到空节点就直接返回了。接下来都是找到删除的节点的情况了：
- 左右孩子都为空，直接删除节点，返回null给上一级
- 左孩子为空，右孩子不为空，删除节点后 右孩子补位，因此返回右孩子给上一级
- 右孩子为空，左孩子不为空，删除节点后 左孩子补位，因此返回左孩子给上一级
- 左右孩子都不为空，则将删除节点左子树的头节点放在 删除节点 右子树的最左边节点上，删除节点的右孩子为新根节点。
完整代码如下：情况二没有在代码里有所体现是因为 它被包含在了情况三四中，因为返回的无论是左节点还是右节点都是空。
class Solution { // Java
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root; // 情况一：没找到删除的节点
if (root.val == key) {
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;
root = root.right;
return root;
}
}
if (root.val > key) root.left = deleteNode(root.left, key); // 继续在左子树中查找
if (root.val < key) root.right = deleteNode(root.right, key); // 继续在右子树中查找
return root;
}
}
复杂度分析：
时间复杂度：O(h). h为树高， 树高决定递归深度
空间复杂度：O(h). h为树高， 同上
