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

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12 
13     /*
14         One step right and then always left
15     */
16     int successor(TreeNode *root) 
17     {
18         root = root->right;
19         while (root->left != NULL) 
20         {
21             root = root->left;            
22         }
23     
24         return root->val;
25     }
26 
27     /*
28         One step left and then always right
29     */
30     int predecessor(TreeNode *root) 
31     {
32         root = root->left;
33         while (root->right != NULL) 
34         {
35             root = root->right;
36         }
37         return root->val;
38     }
39 
40     TreeNode* deleteNode(TreeNode *root, int key) 
41     {
42         if (root == NULL) 
43         {
44             return NULL;
45         }
46 
47         // delete from the right subtree
48         if (key > root->val) 
49         {
50             root->right = deleteNode(root->right, key);
51         }
52         // delete from the left subtree
53         else if (key < root->val) 
54         {
55             root->left = deleteNode(root->left, key);
56         }
57         // delete the current node
58         else 
59         {
60             // the node is a leaf
61             if (root->left == NULL && root->right == NULL) 
62             {
63                 root = NULL;
64             }
65             // the node is not a leaf and has a right child
66             else if (root->right != NULL) 
67             {
68                 root->val = successor(root);
69                 root->right = deleteNode(root->right, root->val);
70             }
71             // the node is not a leaf, has no right child, and has a left child    
72             else 
73             {
74                 root->val = predecessor(root);
75                 root->left = deleteNode(root->left, root->val);
76             }
77         }
78         return root;
79     }
80 };