235. 二叉搜索树的最近公共祖先
关键点：最近公共祖先的判断，二叉树的特性
1、做二叉树的模式
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root is None:
return None
if root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
if not left:
return right
return left
2、二叉搜索树优化,只需要判断一边就可以返回
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root is None:
return None
if root.val > p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
elif root.val < p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
else:
return root
3、迭代法
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while root:
if root.val > p.val and root.val > q.val:
root = root.left
elif root.val < p.val and root.val < q.val:
root = root.right
else:
return root
return None
701.二叉搜索树中的插入操作
赋值需要知道父节点，需要一个指针
1、递归法
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)
if root.val < val:
root.right = self.insertIntoBST(root.right, val)
return root
2、迭代法+指针
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if root is None:
return TreeNode(val)
cur = root
pre = None
while cur:
pre = cur
if cur.val > val:
cur = cur.left
else:
cur = cur.right
if pre.val > val:
pre.left = TreeNode(val)
else:
pre.right = TreeNode(val)
return root
450.删除二叉搜索树中的节点
1、递归法
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if root is None:
return None
if root.val == key:
if not root.right:
return root.left
if not root.left:
return root.right
cur = root.right
while cur.left:
cur = cur.left
cur.left = root.left
return root.right
if root.val > key:
root.left = self.deleteNode(root.left, key)
else:
root.right = self.deleteNode(root.right, key)
return root
2、公共二叉树删除法。选出右节点最左边树的值与删除节点交换
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if root is None:
return None
if root.val == key:
if not root.right:
return root.left # root.left 为 None 也可以返回
cur = root.right
while cur.left:
cur = cur.left
root.val, cur.val = cur.val, root.val # 交换右子树最左节点和根节点的值。
# 后序会遍历到 root.val == key 的逻辑，root.left 与 root.right 都为 None, 可以返回 None。相当与删除了节点
root.left = self.deleteNode(root.left, key)
root.right = self.deleteNode(root.right, key)
return root