问题：

● 235. 二叉搜索树的最近公共祖先
● 701.二叉搜索树中的插入操作
● 450.删除二叉搜索树中的节点

首先，二叉搜索树是一种常见的数据结构，它具有以下特点：

每个节点最多有两个子节点，分别为左子节点和右子节点；
左子节点的值小于父节点的值，右子节点的值大于父节点的值；
没有重复的节点值。

在刷题过程中，我遇到了以下三道题目：

1. 二叉搜索树的最近公共祖先：该题目要求在一个二叉搜索树中，找到两个节点的最近公共祖先。我的解题思路是，从根节点开始遍历二叉搜索树，如果两个节点的值都小于当前节点的值，说明它们都在当前节点的左子树中；如果两个节点的值都大于当前节点的值，说明它们都在当前节点的右子树中；如果一个节点的值小于当前节点的值，另一个节点的值大于当前节点的值，说明它们的最近公共祖先就是当前节点。具体实现可以使用递归或者迭代方式，时间复杂度为O(logn)。
1. 二叉搜索树中的插入操作：该题目要求在一个二叉搜索树中插入一个节点。我的解题思路是，从根节点开始遍历二叉搜索树，如果插入节点的值小于当前节点的值，就去遍历左子树；如果插入节点的值大于当前节点的值，就去遍历右子树。一直遍历到某个节点的左子节点或右子节点为空时，就把插入节点作为该节点的左子节点或右子节点。具体实现可以使用递归或者迭代方式，时间复杂度为O(logn)。
1. 删除二叉搜索树中的节点：该题目要求在一个二叉搜索树中删除一个节点。我的解题思路是，首先找到要删除的节点，如果该节点有两个子节点，就找到它的后继节点（即右子树中最小的节点），把后继节点的值复制到要删除的节点中，然后把要删除的节点变成后继节点；如果该节点只有一个子节点或没有子节点，就直接把该节点删除，并把它的子节点接到它的父节点上。具体实现可以使用递归或者迭代方式，时间复杂度为O(logn)。

总结一下，二叉搜索树是一种非常重要的数据结构，在刷题过程中，我对它的特点和操作有了更深入的理解。对于二叉搜索树的操作，递归和迭代实现都可以，具体选择哪种方式要根据具体情况而定。在Java中，可以使用TreeNode类来表示二叉树节点，具体实现可以参考以下代码：

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 || root == p || root == q) {
            return root;
        }
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else {
            return root;
        }
    }
    
    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 {
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }
    
    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 {
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            } else {
                TreeNode minNode = getMin(root.right);
                root.val = minNode.val;
                root.right = deleteNode(root.right, minNode.val);
            }
        }
        return root;
    }
    
    public TreeNode getMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

秒客网

day22 ● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点

问题：

相关文章