235.二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

和之前二叉树的最近公共祖先相同，只不过二叉搜索树更有规律。
1.当当前节点大于p、q两个节点的值，向左寻找
2.当当前节点小于p、q两个节点的值，向右寻找
3.如果值在他们中间，就说明找到了

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null) {return null;}if (root.val > p.val && root.val > q.val) {TreeNode left = lowestCommonAncestor(root.left, p, q);if (left != null) {return left;}}if (root.val < p.val && root.val < q.val) {TreeNode right = lowestCommonAncestor(root.right, p, q);if (right != null) {return right;}}return root;}
}

701.二叉树搜索中的插入操作

秒了

class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if (root == null) {root = new TreeNode(val);return root;}insert(root, val);return root;}public void insert(TreeNode root, int val) {if (root.left == null && root.val > val) {root.left = new TreeNode(val);}if (root.right == null && root.val < val) {root.right = new TreeNode(val);}if (root.val > val) {insert(root.left, val);}if (root.val < val) {insert(root.right, val);}}
}

450.删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

还是递归，首先需要找到节点，找到节点后，根据左右孩子的情况讨论。而且需要保留它的父节点（也就是root.left=deleteNode()的意义）。
最复杂的是左右孩子都有的节点，这种情况下需要找到该节点右子树的最左边节点（左子树的值肯定比右子树的小），然后把左子树插到最左边。

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) {return null;}// 左孩子为空，右孩子不为空if (root.left == null && root.right != null) {return root.right;}// 右孩子为空，左孩子不为空if (root.right == null && root.left != null) {return root.left;}// 左右孩子都不为空// 找到右孩子的最左节点TreeNode curr = root.right;while (curr.left != null) {curr = curr.left;}// 右子树的最左节点左节点变成左孩子curr.left = root.left;return root.right;}if (root.val > key) {root.left = deleteNode(root.left, key);}if (root.val < key) {root.right = deleteNode(root.right, key);}return root;}
}