秋招算法备战第22天 | 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

在一个二叉搜索树中，两个节点 p 和 q 的最近公共祖先可以通过以下的算法找到：

1. 从根节点开始。
2. 如果当前节点的值大于 p 和 q 的值，那么你需要转向左子树。因为在二叉搜索树中，左子树的所有节点的值都比当前节点的值小。
3. 如果当前节点的值小于 p 和 q 的值，那么你需要转向右子树。因为在二叉搜索树中，右子树的所有节点的值都比当前节点的值大。
4. 如果以上条件都不满足，那么当前节点就是 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）

对于二叉搜索树的删除操作，主要分为以下几个步骤：

1. 找到需要删除的节点；
2. 如果节点是叶子节点，可以直接删除；
3. 如果节点只有一个孩子，可以直接将其父节点的相应链接指向它的孩子；
4. 如果节点有两个孩子，需要找到其右子树的最小节点（或左子树的最大节点），用这个节点代替要删除的节点，然后删除这个最小（或最大）节点。

以下是一个用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 来找到一个树中的最小节点。

总结

今天的题主要是将结点作为返回值，通过遍历过程中更新左右子树来完成对树的操作