力扣236、235、701、450

一、236. 二叉树的最近公共祖先 - 力扣（LeetCode）

1.1题目

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

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

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

1.2思路分析

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

整体思路采用后续递归遍历进行判断，后续遍历：即先左子树再右子树最后再遍历根节点。

则算法的执行流程为：

1、判断当前节点是否等于q或p时或当前节点是否为空时（为空时此次该节点为根节点了）

2、对左子树与右子树进行遍历（采用对整棵树进行遍历）

2、对左子树与右子树遍历的结果进行判断：

a、当左子树与右子树的结果都不为空时，此时在树中找到了pq，则返回根节点

b、当左子树与右子树的结果都为空时，说明此时以该节点为根节点的子树未找到p

、q,则返回空

c、当左子树结果不为空而右子树为空时，说明此时在左子树中找到了p或q则将左子树返回

d、当左子树结果为空而右子树不为空时，说明此时在右子树中找到了p或q则将右子树返回

1.3代码实现

/**
 * 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) {
        // 当根节点为空或者为pq时直接返回
        if( root == null || root == p || root == q ) return root;
//在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返
//回，如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有
//逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）。
        TreeNode left  = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        // 对left与right进行判断
        if(left != null && right != null) return root;
        else if(left != null && right == null) return left;
        else if(left == null && right != null) return right;
        else return null;

    }
}

二、 235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

2.1题目

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

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

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

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉搜索树中。

2.2思路分析 

方法一递归法

方法二迭代法

不管是迭代法还是递归法，判断条件是一样的，都是根据二叉搜索树中根节点的值与P和Q的值及进行判断，无非存在三种情况

a、当前节点的值比q和p的值都大则遍历二叉搜索树中的左子树

b、当前节点的值比q和p的值都小则遍历二叉搜索树中的右子树

d、当前节点的值比q或p的值大或者比q或p的值小，则此时节点的值为最近公共祖先

2.3代码实现

方法一递归法：

/**
 * 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 root;
        // 利用二叉搜索树的性质对树中的节点的值进行判断
        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) {
        // 当前节点不为空时
        while(root != null) {
            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 return root;
        }
        return root;
    }
}

三、701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

3.1题目

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

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

示例 1：

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

提示：

• 树中的节点数将在 [0, 104]的范围内。
• -108 <= Node.val <= 108
• 所有值 Node.val 是 独一无二 的。
• -108 <= val <= 108
• 保证 val 在原始BST中不存在。

3.2思路分析

按照二叉树的遍历规则去遍历，遇到空节点直接插入节点就可以。

3.3代码实现 

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

四、450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

4.1题目

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

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

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

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = [], key = 0
输出: []

提示:

• 节点数的范围 [0, 104].
• -105 <= Node.val <= 105
• 节点值唯一
• root 是合法的二叉搜索树
• -105 <= key <= 105

进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。

4.2思路分析

分为5种情况：

• 第一种情况：没找到删除的节点，遍历到空节点直接返回了
• 找到删除的节点
  • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
  • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
  • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
  • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节具体可以参照这个：代码随想录 (programmercarl.com)

4.3代码实现

/**
 * 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) {
        // 当节点为空节点时，直接返回root
    if(root == null) return root;//第一种情况:没找到删除的节点，遍历到空节点直接返回
    if(root.val == key){
        // 左右孩子都为空直接删除节点，返回空节点
        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 = 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;
    }
}