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

题目描述

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。

示例:

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

另一个正确答案是 [5,2,6,null,4,null,7]。

思路

两个要点：
1.二叉搜索树的搜索树，肯定是小于从left搜索，大于从right搜索，并且递归查询
2.当找到相应的节点后，需要删除。删除后需要从左右任意节点进行重新补充。
3.
（1）如果使用删除节点的左边节点补充，delete_node->left。此时只需要将delete_node->right的节点，重新拼接到delete_node->left节点的最右边节点上，就能保证delete_node->right的所有数据重新满足二叉搜索树条件了。因为
delete_node->left的最右边节点是小于delete_node最大的节点（前驱节点）
（2）如果使用删除节点的右边节点补充，delete_node->right,此时只需要将delete_node->left的节点，重新拼接到delete_node->right节点的最左边节点上，就能保证delete_node->left的所有数据重新满足二叉搜索树条件了，因为
delete_node->right的最左边节点是大于delete_node最小的节点（后继节点）

代码

/**
 * 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(key > root->val){//删除的节点在右子树
            root->right = deleteNode(root->right,key);
            return root;
        }
        if(key < root->val){//删除的节点在左子树
            root->left = deleteNode(root->left,key);
            return root;
        }
        else{//当前节点为待删除节点

            if(root->right != NULL){//删除节点有右子树
                TreeNode* node = root->right;
                while(node->left){
                    node = node->left;//找到大于删除节点最小的节点
                }
                node->left = root->left;//把删除节点的左子树接上去
                return root->right;
            }
            else if(root->left != NULL){//删除节点有左子树
               TreeNode* node = root->left;
               while(node->right){
                   node= node->right;//找到小于删除节点最大的节点
               }
               node->right = root->right;
               return root->left;
            }
            return NULL;
        }
    }
};

复杂度分析

时间复杂度：O(logN)。在算法的执行过程中，我们一直在树上向左或向右移动。首先先用$O(H_1)$O(H1​)的时间找到要删除的节点，$H_1$H1​指从根节点到要删除节点的高度。然后删除节点需要 $O(H_2)$O(H2​)的时间，$H_2$H2​指的是从要删除节点到替换节点的高度。由于$O(H_1 + H_2) = O(H)$O(H1​+H2​)=O(H)指树的高度，若树是一个平衡树则 $H =logN$H=logN。
空间复杂度：$O(H)$O(H)，递归时堆栈使用的空间，$H$H 是树的高度。