代码随想录算法训练营 Day 17
Published:
Q1. LeetCode 235
利用二叉搜索树的性质，当两个节点的值都小于当前节点时，继续遍历左子树；当两个节点的值都大于当前节点时，遍历右子树；否则当前节点为最近公共祖先
解法1. 递归法
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def dfs(node):
if not node:
return node
if node.val > p.val and node.val > q.val:
l = dfs(node.left)
if l:
return l
if node.val < p.val and node.val < q.val:
r = dfs(node.right)
if r:
return r
return node
res = dfs(root)
return res
注意：遍历一条边与遍历整棵树写法的区别
- 遍历一条边
if (递归函数(node.left)) return left if (递归函数(node.right)) return right - 遍历整棵树
left = 递归函数(node.left); right = 递归函数(node.right); left与right的逻辑处理;
解法2: 迭代法
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
Q2. LeetCode 701
不考虑改变树原本结构，利用二叉搜索树性质，找到最下层的节点
解法1: 递归法
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
root = TreeNode(val)
return root
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 not root:
root = TreeNode(val)
return root
curr = root
# 因为最后curr为None，所以需要记录父节点，确保新节点能够与其相连
parent = root
while curr:
parent = curr
if curr.val > val:
curr = curr.left
elif curr.val < val:
curr = curr.right
node = TreeNode(val)
if val < parent.val:
parent.left = node
elif val > parent.val:
parent.right = node
return root
Q3. LeetCode 450
删除节点涉及结构调整。需要考虑的情况：
- 没有找到删除节点 -> 返回空值
- 删除节点为叶子节点 -> 直接删除
- 删除节点只含有左（右）子树 -> 将左（右）子树的父节点更新为当前节点的父节点
- 删除节点包含左右子树 -> 找到比当前节点稍大一点的节点（右子树的最左叶子节点），将左子树插入该节点的左子树
解法1: 递归法
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root:
return root
if root.val == key:
if not root.left and not root.right:
return None
elif not root.left:
return root.right
elif not root.right:
return root.left
else:
# 找到当前节点右子树中最左的叶子节点
curr = root.right
while curr.left:
curr = curr.left
# 将当前节点的左子树整体插入叶子节点的左子树
curr.left = root.left
return root.right
if root.val > key:
root.left = self.deleteNode(root.left, key)
if root.val < key:
root.right = self.deleteNode(root.right, key)
return root
解法2: 迭代法
class Solution:
def deleteOneNode(self, target):
if not target:
return target
if not target.left and not target.right:
return None
elif not target.left:
return target.right
elif not target.right:
return target.left
else:
curr = target.right
while curr.left:
curr = curr.left
curr.left = target.left
return target.right
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root:
return root
curr = root
# 需要变量记录前一个节点
parent = None
while curr:
if curr.val == key:
# 找到删除节点
break
parent = curr
if curr.val > key:
curr = curr.left
elif curr.val < key:
curr = curr.right
# parent为空值，root节点即为删除节点
if not parent:
return self.deleteOneNode(curr)
# 否则parent节点为删除节点的父节点，需要找到左右子树中哪一个为删除节点
# 注意curr节点可能为空，即parent节点为叶子节点，因此需要判断是否有左（右）子树
if parent.left and parent.left.val == key:
parent.left = self.deleteOneNode(curr)
if parent.right and parent.right.val == key:
parent.right = self.deleteOneNode(curr)
return root