Leetcode

二叉搜索树(Binary Search Tree, BST)是具有以下特性的二叉树： 左子树中的所有节点键值小于父节点的键值 右子树中的所有节点键值大于父节点的键值 左右子树本身也必须是二叉搜索树 这些特性使得二叉搜索树成为一种高效的数据结构，特别适合用于搜索、插入和删除操作。 二叉搜索树的操作复杂度 二叉搜索树各种操作的时间复杂度如下： 操作 平均情况 最坏情况 插入 O(log n) O(n) 查找 O(log n) O(n) 删除 O(log n) O(n) 最小值 O(log n) O(n) 最大值 O(log n) O(n) 前驱 O(log n) O(n) 后继 O(log n) O(n) 值得注意的是，平均情况指的是在平衡树上执行操作所需的时间，而最坏情况则是在非平衡树上执行操作所需的时间。当树不平衡时（例如所有节点都在一侧），BST的性能会大幅下降。 Python实现二叉搜索树 让我们用Python来实现一个二叉搜索树。首先，我们需要定义两个基本类：BinarySearchTree和Node。 基本结构 首先，我们定义一个空的BinarySearchTree类： class BinarySearchTree: def __init__(self): self.root = None self.size = 0 def length(self): return self.size def __len__(self): return self.size 接下来，我们定义一个Node类，并实现一些辅助方法： class Node: def __init__(self, key, val, left=None, right=None, parent=None): self.key = key self.payload = val self.leftChild = left self.rightChild = right self.parent = parent def has_left_child(self): return self.leftChild def has_right_child(self): return self.rightChild def is_left_child(self): return self.parent and self.parent.leftChild == self def is_right_child(self): return self.parent and self.parent.rightChild == self def is_root(self): return not self.parent def is_leaf(self): return not (self.rightChild or self.leftChild) def has_any_children(self): return self.rightChild or self.leftChild def has_both_children(self): return self.rightChild and self.leftChild 插入操作 有了基本结构后，我们可以实现插入操作。插入方法put()会检查树是否已有根节点。如果没有，它会创建一个新节点并将其设为根节点；如果已有根节点，则调用私有的递归辅助函数_put()来按照二叉搜索树的属性搜索树并插入新节点： ...

Binary trees are fundamental data structures in computer science that appear frequently in coding interviews and real-world applications. This guide offers a straightforward explanation of binary trees, their implementation in Python, and common problem-solving patterns. What is a Binary Tree? A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and right child. Key characteristics include: Every node contains a value and references to its children (if any) There is exactly one root node (the topmost node) Nodes with no children are called leaf nodes The structure naturally represents hierarchical relationships Binary trees enable efficient searching, insertion, and deletion operations Python Implementation and Basic Operations Node Structure class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val # Node value self.left = left # Left child reference self.right = right # Right child reference Creating a Binary Tree def create_binary_tree(): # Create a simple binary tree root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) return root Basic Operations (for Binary Search Trees) def insert(root, val): """Insert a value into a binary search tree""" if not root: return TreeNode(val) if val < root.val: root.left = insert(root.left, val) else: root.right = insert(root.right, val) return root def search(root, val): """Search for a value in a binary search tree""" if not root or root.val == val: return root if val < root.val: return search(root.left, val) else: return search(root.right, val) Binary Tree Traversals There are four primary ways to traverse a binary tree, each visiting nodes in a different order: ...

LeetCode链接 问题描述 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 你可以认为每种硬币的数量是无限的。 解题思路 动态规划方法 定义 dp[i] 表示组成金额 i 所需的最少硬币数 初始化：dp[0] = 0 (金额0不需要硬币) 状态转移： 对于每个金额 i，遍历所有硬币面额 如果硬币面额 <= i，则 dp[i] = min(dp[i], dp[i - coin] + 1) 最终结果为 dp[amount]，如果仍为初始值则返回-1 复杂度分析 时间复杂度：O(n * m)，其中n是金额，m是硬币种类数 空间复杂度：O(n)，需要存储dp数组 代码实现 class Solution: def coinChange(self, coins: list[int], amount: int) -> int: dp = [float("inf")] * (amount + 1) dp[0] = 0 for coin in coins: for i in range(coin, amount + 1): dp[i] = min(dp[i], dp[i - coin] + 1) return int(dp[amount]) if dp[amount] != float("inf") else -1