网站建设 网站推广2023年火爆的新闻

一、二叉搜索树的最近公共祖先（Leetcode 235）

由于是二叉搜索树，节点的值有严格的顺序关系：左子树的节点值都小于父节点，右子树的节点值都大于父节点。利用这一点，可以在树中更高效地找到最低公共祖先。

class Solution:def traversal(self, cur, p, q):# 递归的基本情况：当前节点为空，返回 Noneif cur is None:return cur# 如果当前节点的值大于 p 和 q 的值，说明 p 和 q 都在左子树中if cur.val > p.val and cur.val > q.val:  # 左left = self.traversal(cur.left, p, q)  # 在左子树中递归查找if left is not None:return left  # 如果左子树中找到了节点，返回该节点# 如果当前节点的值小于 p 和 q 的值，说明 p 和 q 都在右子树中if cur.val < p.val and cur.val < q.val:  # 右right = self.traversal(cur.right, p, q)  # 在右子树中递归查找if right is not None:return right  # 如果右子树中找到了节点，返回该节点# 如果左右子树都不为空，说明 p 和 q 分别在左右子树中return cur  # 返回当前节点，因为当前节点就是它们的最低公共祖先def lowestCommonAncestor(self, root, p, q):return self.traversal(root, p, q)  # 从根节点开始查找 p 和 q 的最低公共祖先

二、二叉搜索树中的插入操作（Leetcode 701）

如果要插入的值小于当前节点的值，应该插入到左子树；如果要插入的值大于当前节点的值，应该插入到右子树。

class Solution:# 插入值 val 到二叉搜索树中def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:# 如果当前节点为空，创建一个新的节点并返回if root is None or root.val == val:return TreeNode(val)  # 创建一个新的 TreeNode 节点，包含插入的值# 如果当前节点值大于 val，则应该将 val 插入到左子树elif root.val > val:# 如果左子树为空，直接插入该值作为左子节点if root.left is None:root.left = TreeNode(val)  # 创建一个新的节点，并赋值给左子节点else:# 如果左子树不为空，递归地在左子树中插入 valself.insertIntoBST(root.left, val)# 如果当前节点值小于 val，则应该将 val 插入到右子树elif root.val < val:# 如果右子树为空，直接插入该值作为右子节点if root.right is None:root.right = TreeNode(val)  # 创建一个新的节点，并赋值给右子节点else:# 如果右子树不为空，递归地在右子树中插入 valself.insertIntoBST(root.right, val)# 返回根节点，确保树的结构未被破坏return root

三、删除二叉搜索树中的节点（Leetcode 450）

删除节点的三种情况：

1、节点没有子节点（叶子节点）：如果节点没有左子树也没有右子树（即叶子节点），直接删除该节点，返回 None，表示当前节点被删除。

2、节点只有右子树：如果节点没有左子树（root.left is None），那么可以用右子树代替当前节点。删除该节点并返回右子节点，实际上是把右子树提升为当前节点的子树。

3、节点只有左子树：如果节点没有右子树（root.right is None），那么可以用左子树代替当前节点。删除该节点并返回左子节点，实际上是把左子树提升为当前节点的子树。

4、节点有两个子树：从当前节点的右子树开始，递归找到右子树中最左的节点（cur.left is None），该节点就是右子树中的最小节点。将该最小节点的左子树指向当前节点的左子树。

返回右子树作为新树的根节点（也就是当前节点被删除，右子树的最小节点替代了它的位置）。

class Solution:# 删除二叉搜索树中的节点def deleteNode(self, root, key):# 如果当前节点为空，返回空# 表示没有找到节点或到达树的末端if root is None:return root# 如果当前节点的值等于要删除的值if root.val == key:# 如果节点没有子节点（叶子节点），直接删除该节点if root.left is None and root.right is None:return None# 如果节点只有右子树，直接返回右子树，删除当前节点elif root.left is None:return root.right# 如果节点只有左子树，直接返回左子树，删除当前节点elif root.right is None:return root.left# 如果节点有两个子树，找到右子树中的最小节点（左子树的最左节点）else:cur = root.right  # 从右子树开始# 寻找右子树中最小的节点（左子树最深的节点）while cur.left is not None:cur = cur.left# 将右子树最小节点的左子树指向当前节点的左子树cur.left = root.left# 返回右子树作为新的根节点，替代当前节点return root.right# 如果当前节点的值大于要删除的值，递归到左子树中删除if root.val > key:root.left = self.deleteNode(root.left, key)# 如果当前节点的值小于要删除的值，递归到右子树中删除if root.val < key:root.right = self.deleteNode(root.right, key)# 返回根节点，确保树的结构未被破坏return root