235. 二叉搜索树的最近公共祖先
题目链接：235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）
思路
本题可以利用二叉搜索树 有序 的特性。
在有序树里，如果判断一个节点的左子树里有p，右子树里有q呢？
因为是有序树，所有 如果 中间节点是 q 和 p 的公共祖先，那么 中节点的数组 一定是在 [p, q]区间的。即 中节点 > p && 中节点 < q 或者 中节点 > q && 中节点 < p。
那么只要从上到下去遍历，遇到 cur节点是数值在[p, q]区间中则一定可以说明该节点cur就是q 和 p的公共祖先。
本题也不涉及到遍历顺序，因为二叉树有序，也不需要对二叉树进行处理，只需要有左和右遍历就行了。
代码
1 //递归法
2 class Solution {
3 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
4 if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
5 if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
6 return root;
7 }
8 }
1 //迭代法
2 class Solution {
3 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
4 while (true) {
5 if (root.val > p.val && root.val > q.val) {
6 root = root.left;
7 } else if (root.val < p.val && root.val < q.val) {
8 root = root.right;
9 } else {
10 break;
11 }
12 }
13 return root;
14 }
15 }
总结
利用好二叉搜索树的性质，因为他的有序性，递归的时候没有中结点的处理逻辑，迭代的时候也是一步到位。
701.二叉搜索树中的插入操作
题目链接：701. 二叉搜索树中的插入操作 - 力扣（LeetCode）
思路
这道题可以不考虑题目中提示所说的改变树的结构的插入方式，只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。
代码
//递归法
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) // 如果当前节点为空，也就意味着val找到了合适的位置，此时创建节点直接返回。
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;
}
}
1 //迭代法
2 class Solution {
3 public TreeNode insertIntoBST(TreeNode root, int val) {
4 if (root == null) return new TreeNode(val);
5 TreeNode newRoot = root;
6 TreeNode pre = root;
7 while (root != null) {
8 pre = root;
9 if (root.val > val) {
10 root = root.left;
11 } else if (root.val < val) {
12 root = root.right;
13 }
14 }
15 if (pre.val > val) {
16 pre.left = new TreeNode(val);
17 } else {
18 pre.right = new TreeNode(val);
19 }
20
21 return newRoot;
22 }
23 }
450.删除二叉搜索树中的节点
题目链接：450. 删除二叉搜索树中的节点 - 力扣（LeetCode）
思路
这道题首先把二叉搜索树中删除节点遇到的情况都搞清楚。
有以下五种情况：
- 第一种情况：没找到删除的节点，遍历到空节点直接返回了
- 找到删除的节点
- 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
- 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
- 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
- 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的 右子树 的 最左面节点 的左孩子上，返回删除节点右孩子为新的根节点。
代码
class Solution {
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;
}
}
通用的二叉树删除结点方式
没有使用搜索树的特性，遍历整棵树，用交换值的操作来删除目标节点。
代码中目标节点（要删除的节点）被操作了两次：
- 第一次是和目标节点的右子树最左面节点交换。
- 第二次直接被NULL覆盖了。
删除操作代码如下：
1 if (root.val = key){
2 if (root.left == null) return right;
3 if (root.right == null) return left;
4 // 以往右为例
5 TreeNode node = root.right;
6 while (node.right != null){
7 node = node.right;
8 }
9 // （第一次) node就指向了最右边的叶子结点，再把叶子结点的值赋给该结点
10 root.val = node.val;
11 // （第二次）再继续向右搜索删除该叶子结点，且删除的是叶子结点的值
12 root.right = delete(root, node.val);
13 }
总结
二叉搜索树递归不用分前中后序，因为他本身就可以看作是排好序的二叉树，且中序遍历的值是升序的。
在解决二叉搜索的时候，大体按以下思路操作
1 public TreeNode traversal(TreeNode root, int key){
2 // 1、返回逻辑
3 if (root == null) 返回情况；
4 // 其余的返回情况，全部列举
5 if...
6 if...
7 // 2、递归逻辑
8 // 只用考虑左方向 -- 并接收左孩子传来的结果
9 if (root.val > key) root.left = traversal(root.left, key);
10 // 右方向同理
11 if (root.val < key) root.right = traversal(root.right, key);
12 // 3、最后递归函数返回值
13 // 通常返回处理好的结果root
14 return root;
15
16 }
标签：right,TreeNode,val,root,二叉,搜索,树中,节点,left From： https://www.cnblogs.com/xpp3/p/17146556.html