450-删除二叉搜索树中的节点

LeetCode 450. Delete Node in a BST

LeetCode-450

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.
Follow up: Can you solve it with time complexity O(height of tree)?

Example 1:

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

method

• 空节点是没找到，直接返回
• key比当前节点值小，往左子树找
• key比当前节点值大，往右子树找

正好等于当前节点值，删除的逻辑

• 左子树空，返回右子树
• 右子树空，返回左子树
• 都不空，把左子树放到右子树的最左边的叶子节点，删掉当前节点，返回右子树节点

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return root;
    if (root->val < key) root->right = deleteNode(root->right, key);
    else if (root->val > key) root->left = deleteNode(root->left, key);
    else {  // 需要删除当前节点
        if (!root->left) return root->right;    // 没有左子树就直接返回右子树
        if (!root->right) return root->left;    // 没有右子树就直接返回左子树
        TreeNode *cur = root->right;
        while (cur->left) cur = cur->left;  // 找到左下角节点
        cur->left = root->left; // 左子树移过去
        TreeNode *tmp = root;
        root = root->right;
        delete tmp; // 删掉头结点
    }
    return root;
}