删除二叉搜索树中的节点

Contents

1. 题目
2. 思路1
1. 2.1. 犯错点
3. 思路2

题目

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。
说明：要求算法时间复杂度为 O(h)，h 为树的高度。
示例:
root = [5,3,6,2,4,null,7]
key = 3
5
/ \
3 6
/ \ \
2 4 7
给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
5
/ \
4 6
/ \
2 7
另一个正确答案是 [5,2,6,null,4,null,7]。
5
/ \
2 6
\ \
4 7

思路1

分几种情况
1.没有左右子树，直接删除
2.只有一个子树，将父指向子，直接删除
3.如果是有父子节点，找到右子树最小的节点，替换

犯错点

1.只有一个元素的时候，删除没考虑好
2.删除根节点没有处理好

思路2

参考别人的算法，自己在后面处理没写好，别人的算法是通过递归的，主要好处就不用找父节点了

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null)return null;
        if(root.val > key){
            root.left =  deleteNode(root.left, key);
            return root;
        }else if(root.val < key){
            root.right = deleteNode(root.right, key);
            return root;
        }else{
            if(root.left == null){
                return root.right;
            }else if(root.right == null){
                return root.left;
            }else{           
                TreeNode successor = minNode(root.right);   
                successor.right = deleteMin(root.right);
                successor.left = root.left;
                return successor;
            }
        }
    }
    private TreeNode minNode(TreeNode node){
        if(node.left == null){          
            return node;
        }
        return minNode(node.left);
        
    }
    private TreeNode deleteMin(TreeNode node){
        if(node.left == null){
            return node.right;
        }
        node.left =  deleteMin(node.left);   
        return node;
        
    }
}

通过递归的方式
1.如果node值大于 key，则递归左子树，返回值覆给左子树
2.如果node值小于key，则递归右子树，返回值覆给右子树
3.相等情况比较复杂
3.1 如果node值等于key，并且左子树为空，那么直接返回右子树，这样就删除了该node。
3.2 如果node值等于key，并且右子树为空，那么直接返回右子树，这样就删除了该node。
3.3 如果node等于key，同时左右都不为空
3.3.1 获取该子树最小的node，命名为successor
3.3.2 将右子树删除最小值，并且将最新的右子树赋值给successor的右子树
3.3.3 将之前节点的左子树赋值给successor的左子树
3.3.4 返回新构建的节点

minNode是返回某个子树的最小值，也就是找最左节点

deleteMin是删除子树的最小值，递归的方式
退出条件是某个节点的左节点是空，则返回右节点，其他情况递归左子树

主要使用了递归的手段，这种手段可以避免找父节点，但我还不是很熟悉，需要继续熟悉递归的思维方式。