Leetcode/delnodeinabst.cpp at main · parallelsolitude/Leetcode · GitHub

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
class Solution
{
public:
    TreeNode *deleteNode(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->right == NULL)
            {
                return NULL;
            }
            else if (root->left == NULL)
            {
                return root->right;
            }
            else if (root->right == NULL)
            {
                return root->left;
            }
            else
            {
                int minVal = getMinVal(root->right);
                root->val = minVal;
                root->right = deleteNode(root->right, minVal);
            }
        }
        return root;
    }

    int getMinVal(TreeNode *root)
    {
        while (root && root->left)
        {
            root = root->left;
        }

        return root->val;
    }
};