LeetCode刷题【450】删除二叉搜索树中的节点

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

一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

说明： 要求算法时间复杂度为 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

题解

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        //最终空节点判断
        if (root==null)return null;
        if (key < root.val){
            //在左子树中继续找了删除key
            root.left = deleteNode(root.left,key);
        }else if ( key > root.val){
            //在右子树中找了删除key
            root.right = deleteNode(root.right,key);
        }else{
            //找到了这个节点
            //如果没有子节点，直接删除当前节点，如果只有一个子节点，把子节点放到当前位置
            if (root.left == null || root.right == null){
                return root.left==null ? root.right : root.left;
            }else{
                //肯定有两个子节点的情况
                TreeNode node = getPre(root);
                //这里取前驱结点的值，给到root节点上
                root.val = node.val;
                //在左子树上删掉移动上来的前驱节点
                root.left = deleteNode(root.left,node.val);
            }
        }
        return root;
    }



    //找到前驱节点
    private TreeNode getPre(TreeNode root){
        TreeNode node = root.left;
        while (node.right!=null){
            node = node.right;
        }
        return node;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

BST的删除基本操作，相关BST的更多操作概念回头补上