235. 二叉搜索树的最近公共祖先
题目简述：
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
思路：
1. 不断遍历，对于最近公共祖先往上的父节点，p和q要么都大于其值，要么都小于
2. 出现了分叉，说明刚好为最近公共祖先
class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: ancestor = root while True: if p.val < ancestor.val and q.val < ancestor.val: ancestor = ancestor.left elif p.val > ancestor.val and q.val > ancestor.val: ancestor = ancestor.right else: break return ancestor
701. 二叉搜索树中的插入操作
题目简述：
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
思路：
1. 当前节点的值不等于val，不断往下
2. 当前节点为None，就插入
3. 利用pre节点进行插入
class Solution: def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]: res=root pre=None if not root: root=TreeNode(val) return root while root: if root.val<val: pre=root root=root.right if not root: pre.right=TreeNode(val) break if root.val>val: pre=root root=root.left if not root: pre.left=TreeNode(val) break return res
450. 删除二叉搜索树中的节点
题目简述：
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。
思路：
递归+细致分类讨论
class Solution: def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]: if root is None: return None if root.val > key: root.left = self.deleteNode(root.left, key) elif root.val < key: root.right = self.deleteNode(root.right, key) elif root.left is None or root.right is None: root = root.left if root.left else root.right else: successor = root.right while successor.left: successor = successor.left successor.right = self.deleteNode(root.right, successor.val) successor.left = root.left return successor return root
纯遍历
1. 需要多个while
2. 细致分类讨论
3. 记录父节点
class Solution: def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]: cur, curParent = root, None while cur and cur.val != key: curParent = cur cur = cur.left if cur.val > key else cur.right if cur is None: return root if cur.left is None and cur.right is None: cur = None elif cur.right is None: cur = cur.left elif cur.left is None: cur = cur.right else: successor, successorParent = cur.right, cur while successor.left: successorParent = successor successor = successor.left if successorParent.val == cur.val: successorParent.right = successor.right else: successorParent.left = successor.right successor.right = cur.right successor.left = cur.left cur = successor if curParent is None:# 意味着cur没有遍历过，key等于第一个节点 return cur if curParent.left and curParent.left.val == key: curParent.left = cur else: curParent.right = cur return root