织梦网站迁移英文网站设计公司
问题：
● 235. 二叉搜索树的最近公共祖先
● 701.二叉搜索树中的插入操作
● 450.删除二叉搜索树中的节点
首先，二叉搜索树是一种常见的数据结构，它具有以下特点：
- 每个节点最多有两个子节点，分别为左子节点和右子节点；
- 左子节点的值小于父节点的值，右子节点的值大于父节点的值；
- 没有重复的节点值。
在刷题过程中，我遇到了以下三道题目：
-
- 二叉搜索树的最近公共祖先：该题目要求在一个二叉搜索树中，找到两个节点的最近公共祖先。我的解题思路是，从根节点开始遍历二叉搜索树，如果两个节点的值都小于当前节点的值，说明它们都在当前节点的左子树中；如果两个节点的值都大于当前节点的值，说明它们都在当前节点的右子树中；如果一个节点的值小于当前节点的值，另一个节点的值大于当前节点的值，说明它们的最近公共祖先就是当前节点。具体实现可以使用递归或者迭代方式，时间复杂度为O(logn)。
-
- 二叉搜索树中的插入操作：该题目要求在一个二叉搜索树中插入一个节点。我的解题思路是，从根节点开始遍历二叉搜索树，如果插入节点的值小于当前节点的值，就去遍历左子树；如果插入节点的值大于当前节点的值，就去遍历右子树。一直遍历到某个节点的左子节点或右子节点为空时，就把插入节点作为该节点的左子节点或右子节点。具体实现可以使用递归或者迭代方式，时间复杂度为O(logn)。
-
- 删除二叉搜索树中的节点：该题目要求在一个二叉搜索树中删除一个节点。我的解题思路是，首先找到要删除的节点，如果该节点有两个子节点，就找到它的后继节点（即右子树中最小的节点），把后继节点的值复制到要删除的节点中，然后把要删除的节点变成后继节点；如果该节点只有一个子节点或没有子节点，就直接把该节点删除，并把它的子节点接到它的父节点上。具体实现可以使用递归或者迭代方式，时间复杂度为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;}
}