房地产开发网站建设,研发网站建设报价,做音响的是哪个网站,深圳网站设计哪家公司好问题#xff1a;
● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点
首先#xff0c;二叉搜索树是一种常见的数据结构#xff0c;它具有以下特点#xff1a;
每个节点最多有两个子节点#xff0c;分别为左子节点和右子节…问题
● 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;}
}
