# LeetCode: 450. 删除二叉搜索树中的节点¶

## 1、题目描述¶

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

root = [5,3,6,2,4,null,7]
key = 3

5
/ \
3   6
/ \   \
2   4   7

5
/ \
4   6
/     \
2       7

5
/ \
2   6
\   \
4   7


## 2、解题思路¶

​ 分几种情况讨论

• 首先寻找当前节点，如果找到，删除节点，并调整树
• 调整树:
• 如果存在右子树，使用右子节点替换当前节点，并判断是否存在左节点，存在的话，右节点的进行找到树中最左节点，将左子树挂在上面
• 如果不存在右子树，当前节点的位置直接由左节点替换
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def deleteNode(self, root, key):
"""
:type root: TreeNode
:type key: int
:rtype: TreeNode
"""

ans = father = TreeNode(0)
father.right = root
cur = root

def search(pre, current, target):

while current:
if current.val == target:
return pre, current
pre = current
if current.val > target:
current = current.left
else:
current = current.right

return None, None

if not current:
return

direction = 0
if pre.right is current:
direction = 1

if not current.left:
if not direction:
pre.left = current.right
else:
pre.right = current.right
return
if not current.right:
if not direction:
pre.left = current.left
else:
pre.right = current.left
return

if not direction:
pre.left = current.right
else:
pre.right = current.right

temp = current.right

while temp.left:
temp = temp.left
temp.left = current.left
return