235. 二叉搜索树的最近公共祖先
题目链接/文章讲解
相对于 二叉树的最近公共祖先 本题就简单一些了，因为 可以利用二叉搜索树的特性。
思路
- 利用二叉搜索树的特性来找
- 如果遍历根节点，如果根节点大于p,q，说明公共节点一定在左子树；
- 如果根节点小于p和q，说明公共节点一定在右子树；
- 如果在p和q之间，说明就是公共祖先（但一定是最近的公共祖先吗？如果公共祖先节点在p和q之间，那么p一定在左子树，q一定在右子树。如果继续向左遍历，将错过p；继续向右遍历，将错过q，所以这一定是最近公共祖先）。
- 本题的迭代法代码也很简单
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//递归
if(root == null) return null;
//这道题不需要涉及前中后序，因为没有处理中间节点
//大于p，q，往左子树搜索
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;
}
}
简洁写法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//递归
if(root == null) return null;
//这道题不需要涉及前中后序，因为没有处理中间节点
//大于p，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;
}
}
迭代法的代码
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
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;
}
}
701.二叉搜索树中的插入操作
题目链接/文章讲解
本题比想象中的简单，大家可以先自己想一想应该怎么做，然后看视频讲解，就发现 本题为什么比较简单了。
思路
- 有多种有效的插入方式，还可以重构二叉搜索树
- 二叉搜索树插入的值都可以在叶子节点找到插入位置，保证有序性即可
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
//终止条件
if(root == null) return new TreeNode(val); // 如果当前节点为空，也就意味着val找到了合适的位置，此时创建节点向上一层返回
//向左遍历
if(val < root.val){
root.left = insertIntoBST(root.left, val); //让原来的节点和插入的节点连接起来
//向右遍历
}else if(val > root.val){
root.right = insertIntoBST(root.right, val);
}
return root;
}
}
450.删除二叉搜索树中的节点
题目链接/文章讲解
相对于 插入操作，本题就有难度了，涉及到改树的结构
思路
- 第一种情况：没找到删除的节点，遍历到空节点直接返回了
- 找到删除的节点
- 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
- 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
- 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
- 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
伪代码思路
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回，返回值是在下面的递归中接住的
if (root.val == key) {
// 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回null为根节点
if (root.left == null && root.right == null) {
return null;
}
// 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
else 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）左子树放在cur的左孩子的位置
root = root.right; // 返回旧root的右孩子作为新root
return root;
}
}
if (root.val > key) root.left = deleteNode(root.left, key);
if (root.val < key) root.right = deleteNode(root.right, key);
return root;
}
没有看普通二叉树的删除方式，二刷再看
