题目简介
● 235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
● 701.二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
● 450.删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。
初见思路
235.想二叉搜索树的特性，根节点左侧均小于它，根节点右侧均大于它。从根节点向下遍历，当节点p、q分别位于根节点左右两侧时，它是二者的最近公共祖先。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
lca = root
while True:
if p.val < lca.val and q.val < lca.val:
lca = lca.left
elif p.val > lca.val and q.val > lca.val:
lca = lca.right
else:
break
return lca
701.插入一个节点到BST中，如果值小于当前节点，一只向左插入直到作为叶子节点；大于当前节点则向右；如果值等于当前节点，那么当前节点值返回;
# 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 not root:
return TreeNode(val)
if val < root.val:
root.left = self.insertIntoBST(root.left, val)
elif val > root.val:
root.right = self.insertIntoBST(root.right, val)
return root
- 这个题目的难点在于删除的逻辑很隐晦，并没有删除值，而是通过赋值的方式实现的。重点是关注对于原子子树（即根左右），删除的逻辑到底是啥样的。
# 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 deleteNode(self, root, key):
if root is None: # 如果根节点为空，直接返回
return root
if root.val == key: # 找到要删除的节点
if root.right is None: # 如果右子树为空，直接返回左子树作为新的根节点
return root.left
cur = root.right
while cur.left: # 找到右子树中的最左节点
cur = cur.left
root.val, cur.val = cur.val, root.val
root.left = self.deleteNode(root.left, key)
root.right = self.deleteNode(root.right, key)
return root
复盘思路
重点难点
BST的删除还可以再看下，多品，多读。
