一.题目描述
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
首先找到需要删除的节点;
如果找到了,删除它。
二.思路分析
整体的思路是利用递归实现,递归遍历二叉树找到节点修改节点并将修改后的节点返回
我感觉这道题在于不同的情况代码分析,因为情况多并且比较复杂.应该可以分成以下的五种情况
1.遍历完所有节点,没有找到目标值直接返回即可最后一层返回NULL
2.找到了目标节点
1).目标节点的左子树右子树都为空(目标节点是叶子节点),此时直接返回NULL即可。
2).目标节点的左子树和右子树有一个不为空
1)).左子树不为空------返回右子树即可。
2)).右子树不为空------返回左子树即可。
3).目标节点的左子树右子树均不为空
这个情况比较复杂,先取出该节点(root)的左孩子,在找到该节点的右子树的最左边的节点把root的左子树接到这个节点
至此五种情况都分析完毕,开始递归三部曲的分析
1).确定参数和返回值----------此题需要初入节点,目标值,因为递归返回节点所以返回值也是节点(TreeNode*,TreeNode*,val)。
2).确定终止条件-----------满足上面五个条件之一即终止
3).确定单层逻辑-----------先将节点值进行判断,当节点值不等于val且节点不为空节点时,判断节点值和目标值的大小并比较,来确定该遍历左子树还是右子树
三.代码实现
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if(root == NULL) return root;if(root-> val == key){if(root -> left == NULL && root -> right == NULL){return NULL;}if(root -> left == NULL || root -> right == NULL){if(root -> left == NULL){return root -> right;}if(root -> right == NULL){return root -> left;}}if(root -> left != NULL && root -> right != NULL){TreeNode* cur = root -> right;while(cur -> left != NULL){cur = cur -> left;}cur->left = root->left;root = root -> right;return root;}}if(root -> val > key)root->left = deleteNode(root->left,key);if(root -> val < key)root->right = deleteNode(root->right,key);return root;}
};