Problem
https://leetcode.com/problems/delete-node-in-a-bst/description/
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
Solution: Recursion
Time complexity: O(h)
Space complexity: O(h)
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 |
// Author: Huahua // Running time: 36 ms /** * 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) { if (root == nullptr) return root; if (key > root->val) { root->right = deleteNode(root->right, key); } else if (key < root->val) { root->left = deleteNode(root->left, key); } else { TreeNode* new_root = nullptr; if (root->left == nullptr) { new_root = root->right; } else if (root->right == nullptr) { new_root = root->left; } else { // Find the min node in the right sub tree TreeNode* parent = root; new_root = root->right; while (new_root->left != nullptr) { parent = new_root; new_root = new_root->left; } if (parent != root) { parent->left = new_root->right; new_root->right = root->right; } new_root->left = root->left; } delete root; return new_root; } return root; } }; |
v2
|
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 |
// Author: Huahua // Running time: 35 ms class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if (root == nullptr) return root; if (key > root->val) { root->right = deleteNode(root->right, key); } else if (key < root->val) { root->left = deleteNode(root->left, key); } else { if (root->left != nullptr && root->right != nullptr) { TreeNode* min = root->right; while (min->left != nullptr) min = min->left; root->val = min->val; root->right = deleteNode(root->right, min->val); } else { TreeNode* new_root = root->left == nullptr ? root->right : root->left; root->left = root->right = nullptr; delete root; return new_root; } } return root; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment