(BST二叉搜索树 1.2)Leetcode Delete no in a BST(删除二叉搜索树中的节点)

小鱼儿 2022-02-28 00:34 336阅读 0赞

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:

1.  Search for a node to remove.
2.  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
    
    Another valid answer is [5,2,6,null,4,null,7].
    
        5
       / \
      2   6
       \   \
        4   7

> /\*\*  
> \* Definition for a binary tree node.  
> \* struct TreeNode \{  
> \* int val;  
> \* struct TreeNode \*left;  
> \* struct TreeNode \*right;  
> \* \};  
> \*/  
> struct TreeNode\* deleteNode(struct TreeNode\* root, int key) \{  
> //如果节点为空,返回空  
> if(root == NULL)\{  
> return NULL;  
> \}  
>   
> //如果需要删除的节点 < 根节点的值  
> if(key < root->val)\{  
> //在左子树递归删除该节点  
> root->left = deleteNode(root->left,key);  
> \}else if(key > root->val)\{//如果需要删除的节点 > 根节点的值  
> //在右子树递归删除该节点  
> root->right = deleteNode(root->right,key);  
> \}else\{//如果当前节点就是需要删除的节点  
>   
> /\*  
> 如果是单边节点  
> \*/  
> //如果左子树为空  
> if(root->left == NULL)\{  
> //直接删除根节点,将root直接指向右子树  
> root = root->right;  
> \}else if(root->right == NULL)\{//如果右子树为空  
> //直接删除根节点,将root直接指向左子树  
> root = root->left;  
> \}else\{  
>   
> /\*  
> 所有该节点拥有左右子树  
> \*/  
> //寻找该节点的右子树的最右节点  
> struct TreeNode\* cur = root->right;  
> while(cur->left)\{  
> cur = cur->left;  
> \}  
> //将右子树的最左孩子节点的值付给根节点  
> root->val = cur->val;  
> //然后删除该节点  
> root->right = deleteNode(root->right,cur->val);  
> \}  
> \}  
>   
> return root;  
> \}