设计网站导航大全,2022年国际新闻,wordpress仿站教程,dede页码的调用 网站一、二叉搜索树的最近公共祖先#xff08;Leetcode 235#xff09; 由于是二叉搜索树#xff0c;节点的值有严格的顺序关系#xff1a;左子树的节点值都小于父节点#xff0c;右子树的节点值都大于父节点。利用这一点#xff0c;可以在树中更高效地找到最低公共祖先。
c…一、二叉搜索树的最近公共祖先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
