450. Delete Node in a BST

1.問題

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