235 二叉搜索树的最近公共祖先
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
ret=root
while True:
if ret.val<p.val and ret.val <q.val:
ret=ret.right
elif ret.val>p.val and ret.val >q.val:
ret=ret.left
else:
break
return ret
701 二叉搜索树中的插入操作
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return TreeNode(val)
pos=root
while pos:
if pos.val<val:
if not pos.right:
pos.right=TreeNode(val)
break
else:
pos=pos.right
else:
if not pos.left:
pos.left=TreeNode(val)
break
else:
pos=pos.left
return root
450 删除二叉搜索树中的节点
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 not root.left or not root.right:
root = root.left if root.left else root.right
else:
t=root.right
while t.left:
t=t.left
t.right=self.deleteNode(root.right,t.val)
t.left=root.left
return t
return root
