算法训练营day21 | {235.二叉搜索树的最近公共祖先, 701.二叉搜索树中的插入操作, 450.删除二叉搜索树中的节点}

第六章二叉树part07，找二叉搜索树的最近公共祖先原来是前序遍历。

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

1.1 递归法

  • 本题其实和在一个二叉搜索树中查找指定的值思路一样，也适合用前序遍历，当发现一个节点刚好在节点p和节点q时，它必定是两节点的公共祖先，同时也是最近祖先。

  • 分析递归三步曲：

    1. 参数和返回值是什么？ 要传入一个根节点，指定的节点p、节点q；返回值是找到的祖先节点
    2. 确定递归的终止条件。 如果当前节点为空节点，则返回。
    3. 确定单层递归的逻辑。 前序遍历，中左右，很简单的比较吧~

  • 前序遍历–递归

    1
    2
    3
    4
    5
    6
    7
    8
    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) return null;
            if(Math.min(p.val, q.val) <= root.val && root.val <= Math.max(p.val, q.val)) return root;
            else if (Math.max(p.val, q.val) < root.val) return lowestCommonAncestor(root.left, p, q);
            return lowestCommonAncestor(root.right, p, q);
        }
    }

1.2 迭代法

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int rightVal = Math.max(p.val, q.val);
        int leftVal = Math.min(p.val, q.val);
        while (root != null) {
            if (leftVal <= root.val && root.val <= rightVal) return root;
            else if (rightVal < root.val) root = root.left;
            else root = root.right;
        }
        return null;
    }
}

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

2.1 解题分析

  • 迭代法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
        public TreeNode insertIntoBST(TreeNode root, int val) {
            TreeNode cur = root, pre = null;
            while (cur != null) {
                pre = cur;
                if (val < cur.val) cur = cur.left;
                else cur = cur.right;
            }
            if (pre == null) return new TreeNode(val);
            else if (pre.val > val) pre.left = new TreeNode(val);
            else pre.right = new TreeNode(val);
            return root;
        }
    }

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

3.1 解题分析

  • 遍历只要保证左右就可以了，前序遍历

  • 本题不需要遍历整个树，找到要删除的节点删除后就终止了，以下是终止情况的讨论：

    1. 没找到要删除的key节点
    2. 要删除的节点是叶子节点
    3. 要删除的节点 左不空，右空
    4. 要删除的节点 左空，右不空
    5. 要删除的节点 左不空，右也不空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        else if (root.val == key) {
            if (root.left == null && root.right == null) return null;
            else if (root.left != null && root.right == null) return root.left;
            else if (root.left == null && root.right != null) return root.right;
            else {
                TreeNode cur = root.right;
                while (cur.left != null) cur = cur.left;
                cur.left = root.left;
                return root.right;
            }
        }
        if (key < root.val) root.left = deleteNode(root.left, key);
        if (key > root.val) root.right = deleteNode(root.right, key);
        return root;
    }
}

注意左不空，右也不空时，还是和平衡二叉树的删除不太一样的，那个还要中序遍历找最近的节点，并且左旋右旋。本题比较暴力，不过题不要做复杂了。

5. 今日收获

  • 继续二叉搜索树的练习，多思考、多利用二叉搜索树的特性解题。
  • 学习时长：2小时
Leetcode > 二叉树
#Java #代码随想录
算法训练营day21 | {235.二叉搜索树的最近公共祖先, 701.二叉搜索树中的插入操作, 450.删除二叉搜索树中的节点}
http://paopaotangzu.xyz/cn/day21_leetcode/
作者
PROTON TANG
发布于
2026年1月6日
许可协议