大连凯杰建设有限公司网站如何去除痘痘有效果
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, val=0, left=None, right=None):
# 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_child=False):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_child=True)else:traversal(cur.right, val)traversal(root, val)return root
下面是GPT4对该代码的优化
你的代码已经很好地实现了插入操作。你在遍历树的时候,递归地找到插入节点的位置,然后创建新节点并插入到正确的位置。同时,你用一个外部变量
pre
来跟踪上一个节点,以便在正确的位置插入新节点。然而,你的代码可以被优化,使其更简洁和易于理解。在优化后的代码中,你可以使用返回值,而不是外部变量来跟踪插入的位置。这样,你可以避免使用
nonlocal
关键字,并使函数的逻辑更加清晰。以下是优化后的代码:# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # 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, val=0, left=None, right=None):
# 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
来找到一个树中的最小节点。
总结
今天的题主要是将结点作为返回值,通过遍历过程中更新左右子树来完成对树的操作