leetcode解题: Delete Node in a BST (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.
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

解法1：

此题比较复杂，参考了这篇的解法。主要的思路是把要删除的节点分情况讨论。
基本的思路是： 对于一个要删除的节点，找出大于他的最小的node作为新的子root，或者是选出小于他的最大的node作为新的root。
解决此题的步骤如下：

  1. 找出要删除的节点的父节点。
  2. 如果删除节点是leaf， 那么直接把父节点相应的连接设为null
  3. 如果删除节点只有一个子树， 那么把父节点指向唯一的那个子树
  4. 如果删除节点有两个子树， 那么找出大于删除节点的最小节点（设为x), 然后把删除节点的数值设为x的值，然后重新运行一遍删除操作。
  5. 上一步中，程序一定会终止因为最左节点一定是只有小于等于1个子节点。
    等找出最小的大于他的node的时候（也就是右子树的最左节点）， 要分
    C++
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    /**
     * 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) {
            TreeNode* dummy = new TreeNode(0);
            dummy->left = root;
            
            TreeNode* parent = findNode(dummy, root, key);
            TreeNode* node;
            if (parent->left && parent->left->val == key) {
                node = parent->left;
            } else if (parent->right && parent->right->val == key) {
                node = parent->right;
            } else {
                // can't find the node
                return dummy->left;
            }
            
            deleteNode(parent, node);
            
            TreeNode* res = dummy->left;
            delete dummy;
            return res;
            
        }
        
        TreeNode* findNode(TreeNode* parent, TreeNode* cur,int key) {
            if (!cur || cur->val == key) {
                return parent;
            }
            
            if (cur->val < key) {
                return findNode(cur, cur->right, key);
            } else {
                return findNode(cur, cur->left, key);
            }
        }
        
        void deleteNode(TreeNode* parent, TreeNode* node) {
            // delete the node, giving the parent
             if (!node->right) {
                if (parent->left == node) {
                    parent->left = node->left;
                } else {
                    parent->right = node->left;
                }
            } else if (!node->left) {
                if (parent->left == node) {
                    parent->left = node->right;
                } else {
                    parent->right = node->right;
                }
            } else {
                TreeNode* father = node;
                TreeNode* child = node->right;
                while (child->left) {
                    father = child;
                    child = child->left;
                }
                node->val = child->val;
                deleteNode(father, child);
            }
        }
        
        
    };

Java

1