题目要求:给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
思路:首先要删除二叉搜索树中的节点,第一步就是找到此节点,如果遍历到空就直接返回。删除时可能有以下几种情况:
1.为叶子节点(左右孩子均空),直接删除即可
2.左子树不空右子树空(或左子树空右子树不空),删除节点,将其左孩子(右孩子)进行补位
3.左右孩子均不空,此时应该将删除节点的左孩子(或右孩子)放到删除节点的右子树最左节点的左孩子上(左子树最右节点的右孩子上)
leetcode实战:
代码实现:
递归法:
迭代法: