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

 

代码随想录

力扣传送门

解题思路

分5种情况，第一种是翻个底朝天都找不到node-val==key的，说明删除不了，返回空指针。第2、3、4、5种情况是找到了node->val == key的，那么根据节点的左右孩子是否存在进行了讨论。最复杂的是左右孩子都不为空的。需要将节点的左孩子，放到节点的右孩子的最左边（所以先要找到这个最左孩子），作为左孩子（这段结合Carl的图自己画画就直观了）。后面的就是node->val跟key的比较，然后用左孩子或者右孩子去接住对应递归的结果。其实不需要删除tmp节点对本题的提交没有影响，但是会影响效率，我觉着是因为造成了数据的冗余吧

 

/** * 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 == nullptr) return nullptr; //情况1：没找到key if(root->val == key){ //找到key：分 4种情况 if(root->left == nullptr && root->right == nullptr) return nullptr; //情况2 else if(root->left != nullptr && root->right == nullptr) root = root->left; //情况3 else if(root->left == nullptr && root->right != nullptr) root = root->right; //情况4 else{ //情况4：root左右子树都不为空，要将root左子树放到root右子树的最左子树下面 TreeNode *cur = root->right; while(cur->left != nullptr){ //找到root右子树的最左子树 cur = cur->left; } cur->left = root->left; TreeNode *tmp = root; //保存root,用来后面删除， root = root->right; delete tmp; //因为root改变了，原来处于root的指针结构就要去删除释放,如果不释放也行，对本题不影响结果，但是会存在结构冗余 } } if(key < root->val) root->left = deleteNode(root->left, key); if(key > root->val) root->right = deleteNode(root->right, key); return root; } };