LeetCodeProblems/deleteNodeInBST.cpp at main · iambharatks/LeetCodeProblems · 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
51
52
#include <bits/stdc++.h>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution
{
public:
    TreeNode *minValueNode(TreeNode *root)
    {
        TreeNode *current = root;
        while (current && current->left)
            current = current->left;
        return current;
    }
    TreeNode *deleteNode(TreeNode *root, int key)
    {
        if (!root)
            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)
            {
                TreeNode *tmp = root->right;
                // free(root);
                return tmp;
            }
            if (root->right == NULL)
            {
                TreeNode *tmp = root->left;
                // free(root);
                return tmp;
            }
            TreeNode *tmp = minValueNode(root->right);
            root->val = tmp->val;
            root->right = deleteNode(root->right, tmp->val);
        }
        return root;
    }
};