网站信息,用别人家网站做跳转,宜昌市住房和城乡建设局网站,263企业邮箱注册申请235. 二叉搜索树的最近公共祖先 - 力扣#xff08;LeetCode#xff09;
在一个二叉搜索树中#xff0c;两个节点 p 和 q 的最近公共祖先可以通过以下的算法找到#xff1a;
从根节点开始。如果当前节点的值大于 p 和 q 的值#xff0c;那么你需要转向左子树。因为在二叉…235. 二叉搜索树的最近公共祖先 - 力扣LeetCode
在一个二叉搜索树中两个节点 p 和 q 的最近公共祖先可以通过以下的算法找到
从根节点开始。如果当前节点的值大于 p 和 q 的值那么你需要转向左子树。因为在二叉搜索树中左子树的所有节点的值都比当前节点的值小。如果当前节点的值小于 p 和 q 的值那么你需要转向右子树。因为在二叉搜索树中右子树的所有节点的值都比当前节点的值大。如果以上条件都不满足那么当前节点就是 p 和 q 的最近公共祖先。
在 Python 中这个算法可以像这样实现
class TreeNode:def __init__(self, x):self.val xself.left Noneself.right Nonedef lowestCommonAncestor(root, p, q):while root:if root.val p.val and root.val q.val:root root.leftelif root.val p.val and root.val q.val:root root.rightelse:return rootreturn None在这个代码中lowestCommonAncestor 函数将接受一个二叉搜索树的根节点 root和两个需要找最近公共祖先的节点 p 和 q。然后它将返回 p 和 q 的最近公共祖先。如果没有找到那么它将返回 None。
注意这个算法假设 p 和 q 都在这棵二叉搜索树中。
701. 二叉搜索树中的插入操作 - 力扣LeetCode
因为是二叉树直接按照规则遍历然后在对应叶子结点插入
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def insertIntoBST(self, root: Optional[TreeNode], val: int) - Optional[TreeNode]:if root is None:return TreeNode(val)pre Nonedef traversal(cur, val, left_childFalse):nonlocal preif cur is None:if left_child:pre.left TreeNode(val)else:pre.right TreeNode(val)returnpre curif cur.val val:traversal(cur.left, val, left_childTrue)else:traversal(cur.right, val)traversal(root, val)return root下面是GPT4对该代码的优化 你的代码已经很好地实现了插入操作。你在遍历树的时候递归地找到插入节点的位置然后创建新节点并插入到正确的位置。同时你用一个外部变量 pre 来跟踪上一个节点以便在正确的位置插入新节点。 然而你的代码可以被优化使其更简洁和易于理解。在优化后的代码中你可以使用返回值而不是外部变量来跟踪插入的位置。这样你可以避免使用 nonlocal 关键字并使函数的逻辑更加清晰。以下是优化后的代码 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right class Solution:def insertIntoBST(self, root: Optional[TreeNode], val: int) - Optional[TreeNode]:if root is None:return TreeNode(val)if root.val val:root.left self.insertIntoBST(root.left, val)else:root.right self.insertIntoBST(root.right, val)return root 在优化后的代码中插入新节点的逻辑被分配给递归调用的返回值这使得代码更加简洁并且逻辑更加清晰。这个函数将创建一个新的 TreeNode
如果 root 是 None否则它将递归地遍历左子树或右子树根据 val
的值决定向哪个方向遍历。然后递归调用的返回值即新节点或现有节点被分配给 root.left 或
root.right从而实现插入操作。最后函数返回 root它现在可能有一个新的子节点。450. 删除二叉搜索树中的节点 - 力扣LeetCode
对于二叉搜索树的删除操作主要分为以下几个步骤
找到需要删除的节点如果节点是叶子节点可以直接删除如果节点只有一个孩子可以直接将其父节点的相应链接指向它的孩子如果节点有两个孩子需要找到其右子树的最小节点或左子树的最大节点用这个节点代替要删除的节点然后删除这个最小或最大节点。
以下是一个用Python实现的例子
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right rightclass Solution:def deleteNode(self, root: Optional[TreeNode], key: int) - Optional[TreeNode]:if not root:return Noneif key root.val: # key在左子树root.left self.deleteNode(root.left, key)elif key root.val: # key在右子树root.right self.deleteNode(root.right, key)else: # 找到key进行删除操作if not root.left: # 左子树为空直接返回右子树return root.rightif not root.right: # 右子树为空直接返回左子树return root.leftelse: # 左右子树均不为空min_node self.findMin(root.right) # 找到右子树的最小节点root.val min_node.val # 将最小节点的值复制到rootroot.right self.deleteNode(root.right, min_node.val) # 删除右子树中的最小节点return rootdef findMin(self, node: Optional[TreeNode]) - Optional[TreeNode]:# 找到树中的最小节点while node.left:node node.leftreturn node这个函数的思路主要是使用递归来找到要删除的节点然后按照上面提到的规则删除。在这个过程中我们使用了一个辅助函数 findMin 来找到一个树中的最小节点。
总结
今天的题主要是将结点作为返回值通过遍历过程中更新左右子树来完成对树的操作
