巴州区建设局网站,公司内部网站创建,wordpress默认登录,搜狗网站入口【二叉搜索树】【递归】【迭代】Leetcode 700. 二叉搜索树中的搜索 二叉搜索树解法1 递归法解法2 迭代法 ---------------#x1f388;#x1f388;题目链接#x1f388;#x1f388;-------------------
二叉搜索树 二叉搜索树#xff08;Binary Search Tree#xff… 【二叉搜索树】【递归】【迭代】Leetcode 700. 二叉搜索树中的搜索 二叉搜索树解法1 递归法解法2 迭代法 ---------------题目链接-------------------
二叉搜索树 二叉搜索树Binary Search TreeBST是一种特殊的二叉树具有以下性质
有序性 对于二叉搜索树中的每个节点其左子树中的所有节点的值都小于该节点的值而右子树中的所有节点的值都大于该节点的值。这意味着对于任何节点其左子树中的值都小于该节点的值右子树中的值都大于该节点的值。
唯一性 二叉搜索树中不存在重复的节点。
搜索操作 由于二叉搜索树的有序性可以利用二分查找的思想进行快速的搜索。给定一个值可以从根节点开始比较根据比较结果决定是向左子树还是向右子树搜索直到找到目标节点或者搜索到叶子节点为止。
插入操作 插入操作也是根据节点值的大小关系进行的。从根节点开始比较要插入的节点值与当前节点值的大小关系如果小于当前节点值则继续在左子树中插入如果大于当前节点值则继续在右子树中插入。直到找到合适的位置插入新节点。
删除操作 删除操作相对复杂一些。如果要删除的节点是叶子节点则可以直接删除如果要删除的节点只有一个子节点则将其子节点替换到被删除节点的位置如果要删除的节点有两个子节点则通常选择该节点的前驱节点或者后继节点来替换被删除节点并递归地删除用于替换的节点。
二叉搜索树的这些性质使得其在搜索、插入和删除等操作上具有较高的效率。然而如果树的结构不平衡比如极端情况下树退化成链表则操作的时间复杂度可能会退化到O(n)而不再是平衡状态下的O(log n)。因此在实际应用中通常会考虑使用平衡二叉搜索树如AVL树、红黑树等来保持搜索性能的稳定。 解法1 递归法
时间复杂度在最坏情况下时间复杂度为 O(h)其中 h 是树的高度。在一个平衡的二叉搜索树中树的高度近似为 log(n)其中 n 是树中节点的数量。但是在最坏情况下树可能会退化成链表高度为 n。因此在最坏情况下时间复杂度为 O(n)在平均情况下为 O(log n)。
空间复杂度递归调用的栈空间取决于树的高度因此空间复杂度也是 O(h)。在最坏情况下树可能会退化成链表空间复杂度为 O(n)在平均情况下为 O(log n)。 /*** 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 searchBST(TreeNode root, int val) {return helper(root,val);}public TreeNode helper(TreeNode root, int val){if(root null) return null;if(root.val val) return root;else if(root.valval) {return searchBST(root.left,val);}else {return searchBST(root.right,val);} }
}解法2 迭代法
时间复杂度在最坏情况下时间复杂度为 O(h)其中 h 是树的高度。在一个平衡的二叉搜索树中树的高度近似为 log(n)其中 n 是树中节点的数量。但是在最坏情况下树可能会退化成链表高度为 n。因此在最坏情况下时间复杂度为 O(n)在平均情况下为 O(log n)。
空间复杂度这种迭代方法不使用递归只使用了常量级的额外空间因此空间复杂度是 O(1)。
/*** 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 searchBST(TreeNode root, int val) {// 迭代法while(root ! null){if(root.val val){root root.left;}else if(root.val val){root root.right;}else{return root;}}return null;}
}
