算法训练营Day20

#Java #二叉树

开源学习资料

Feeling and experiences：

二叉搜索树的最近公共祖先:力扣题目链接

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

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

思路：

? 初始化一个指针?node，从根节点?root?开始。
? 使用循环，当?p?和?q?都小于?node.val?时，说明它们都在?node?的左子树上，因此将?node?更新为?node.left。
? 如果?p?和?q?都大于?node.val，说明它们都在?node?的右子树上，因此将?node?更新为?node.right。
? 如果以上两种情况都不成立，说明当前?node?是?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) {
        TreeNode node = root;
        while(true){
            if(p.val < node.val && q.val < node.val){
                node = node.left;
            }else if(p.val > node.val && q.val > node.val){
                node = node.right;
            }
            else{
                break;
            }
        }
        return node;
    }
}

?

二叉搜索树中的插入操作： 力扣题目链接

给定二叉搜索树（BST）的根节点?root?和要插入树中的值?value?，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

1. 基本原则：

在二叉搜索树中插入一个新值时，需要保持二叉搜索树的性质。即对于任何节点，其左子树中所有节点的值都比它小，右子树中所有节点的值都比它大。

2. 递归插入：
? 递归基准情况：如果当前节点为?null（表示到达了应该插入新节点的位置），创建一个新的?TreeNode，其值为?val，然后返回这个新节点。

? 递归搜索：
? 如果?val?小于当前节点的值，表示应该在当前节点的左子树中继续寻找插入位置。对当前节点的左子树?(root.left)?调用?insertIntoBST?方法。
? 如果?val?大于当前节点的值，表示应该在当前节点的右子树中继续寻找插入位置。对当前节点的右子树?(root.right)?调用?insertIntoBST?方法。

3. 更新子树链接：在每一层递归中，根据返回的新树的根节点更新当前节点的左或右子节点链接。

4. 返回结果：最终，递归的根调用将返回更新后的树的根节点。

代码如下：

/**
 * 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);
   }
   if(val < root.val){
       root.left = insertIntoBST(root.left,val);
   }else if(val > root.val){
       root.right = insertIntoBST(root.right , val);
   }
   return root;
    }
}

删除二叉搜索树中的节点：力扣题目链接

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

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

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

关键点：删除了该节点后，要对二叉搜索树进行维护，保持其性质。

/**
 * 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 deleteNode(TreeNode root, int key) {
   
    if (root == null) return null;

    // 查找要删除的节点
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        // 找到了要删除的节点
        // 情况1: 只有一个子节点或没有子节点
        if (root.left == null) {
            return root.right;
        } else if (root.right == null) {
            return root.left;
        }

        // 情况2: 有两个子节点
        TreeNode minNode = findMin(root.right);
        root.val = minNode.val;
        root.right = deleteNode(root.right, root.val);
    }
    return root;
}

private TreeNode findMin(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

    
}

整体思路如下：

1. 查找要删除的节点：
? 如果要删除的节点值小于当前节点的值，向左子树递归。
? 如果要删除的节点值大于当前节点的值，向右子树递归。
? 如果要删除的节点值等于当前节点的值，那么这个节点就是我们要删除的节点。
2. 删除节点：一旦找到要删除的节点，有三种情况：
? 叶子节点（没有子节点）：直接删除该节点，返回?null。
? 只有一个子节点：删除该节点，并返回其唯一的子节点作为新的子树的根。
? 有两个子节点：需要找到要删除节点的右子树中的最小节点（或左子树中的最大节点），这个节点将替换要删除的节点。然后递归地删除那个最小（或最大）节点。
3. 维持BST的性质：在删除节点后，需要通过调整树的结构来保持二叉搜索树的性质。

云青青兮欲雨，

水澹澹兮生烟~

Fighting！
?

?

?

?

?