# 450. Delete Node in a BST

## 1.問題

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LKMECPlMRGOGUE-LIqI%2F-LKMYEbRpOImKhu9P4IZ%2F2018082003.jpg?alt=media\&token=dbe998de-3ccc-4801-9ed1-0f9677c523a9)

## 2.想法

* 當左右子都存在時, 取右子樹的最左子移到root, 並且刪除右子樹

## 3.程式碼

```
/**
 * 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 == NULL ) {
            return NULL;
        }
        
        if (root->val < key) {
            //traverse
            root->right = deleteNode(root->right, key);
        } else if (root->val > key) {
            //traverse
            root->left = deleteNode(root->left, key);
        } else {
            //Remove
            if (root->left == NULL &&
                root->right == NULL) {
                return NULL;
            } else if (root->left == NULL) {
                return root->right;
            } else if (root->right == NULL) {
                return root->left;
            } else {
                TreeNode *tmp = root->right;
                while (tmp->left) {
                    tmp = tmp->left;
                }
                root->val = tmp->val;
                root->right = deleteNode(root->right, root->val);
            }
        }
        
        return root;
    }
};
```

## 4.Performance

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LKMECPlMRGOGUE-LIqI%2F-LKMYRfkw0u_uYD7A1sV%2F2018082004.jpg?alt=media\&token=d9de3ed7-996b-4451-ac3c-288e8dd1f049)