# 450. Delete Node in a BST 删除二叉搜索树中的节点

@TOC

## # 题目描述

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

• Search for a node to remove.
• If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

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

key = 3

5
/ \
3   6
/ \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

5
/ \
4   6
/     \
2       7

5
/ \
2   6
\   \
4   7
``````

## # 解题方法

### # 迭代

1. 被删除节点没有左子树：返回其右子树
2. 被删除节点节点没有右子树：返回其左子树
3. 被删除节点既有左子树，又有右子树： 1）查找到其右子树的最小值的节点，替换掉被删除的节点，并删除找到的最小节点 2）查找到其左子树的最大值的节点，替换掉被删除的节点，并删除找到的最大节点

Python代码如下：

``````# 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
"""
if not root: return None
if root.val == key:
if not root.right:
left = root.left
return left
else:
right = root.right
while right.left:
right = right.left
root.val, right.val = right.val, root.val
root.left = self.deleteNode(root.left, key)
root.right = self.deleteNode(root.right, key)
return root
``````

C++代码如下：

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
if (root->val == key) {
if (!root->left) {
return root->right;
} else {
TreeNode* left = root->left;
while (left->right) {
left = left->right;
}
swap(left->val, root->val);
}
}
root->left = deleteNode(root->left, key);
root->right = deleteNode(root->right, key);
return root;
}
};
``````

## # 日期

2018 年 3 月 23 日 —— 科目一考了100分哈哈哈哈～嗝～ 2019 年 9 月 27 日 —— 昨天面快手，竟然是纯刷题