题目标题

二叉搜索树中删除指定节点

参考解析
  1. class Solution(object):
  2. def deleteNode(self, root, key):
  3. """
  4. :type root: TreeNode
  5. :type key: int
  6. :rtype: TreeNode
  7. """
  8. if not root:
  9. return None
  10. #到左子树里搜索
  11. if root.val > key:
  12. root.left = self.deleteNode(root.left, key)
  13. #到右子树里搜索
  14. elif root.val < key:
  15. root.right = self.deleteNode(root.right, key)
  16. else:
  17. # 存在的子树代替根节点
  18. if not root.left or not root.right:
  19. root = root.left if root.left else root.right
  20. else:
  21. temp = root.right
  22. # 找到右子树的最小(最左)节点
  23. while temp.left:
  24. temp = temp.left
  25. root.val = temp.val
  26. # 继续在右子树里递归
  27. root.right = self.deleteNode(root.right, temp.val)
  28. return root