题目链接:https://leetcode.cn/problems/delete-node-in-a-bst/
这个题目自己没做出来,看的官方题解,最后一步successor找到之后再删除最后返回新的root这段没怎么看明白。
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 |
/** * Definition for a binary tree node. * 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* deleteNode(TreeNode* root, int key) { if (!root) { return nullptr; } if (root->val > key) { root->left = deleteNode(root->left, key); return root; } if (root->val < key) { root->right = deleteNode(root->right, key); return root; } if (root->val == key) { if (!root->left && !root->right) { return nullptr; } if (!root->left) { return root->right; } if (!root->right) { return root->left; } TreeNode* successor = root->right; while (successor->left) { successor = successor->left; } root->right = deleteNode(root->right, successor->val); root->val = successor->val; return root; } return root; } }; |