删除二叉树中的节点

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

示例：
输入
[5,3,6,2,4,null,7]
3
输出
[5,4,6,2,null,null,7]

Java代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //寻找后继节点:先取当前节点的右节点，然后一直取该节点的左节点，直到左节点为空，最后指向的节点即为后继节点
    public int successor(TreeNode root) {
        root = root.right;
        while(root.left != null) root = root.left;
        return root.val;
    }

    //寻找前驱节点：先取当前节点的左节点，然后一直取该节点的右节点，直到右节点为空，最后指向的节点即为前驱节点
    public int predecessor(TreeNode root) {
        root = root.left;
        while(root.right != null) root = root.right;
        return root.val;
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        //递归终止条件
        if(root == null) return null;

        //查找的节点比根节点大，则继续在右子树查找并删除该节点
        if(key > root.val) {
            root.right = deleteNode(root.right, key);
        } else if(key < root.val) {  //如果查找的结点比根节点小，继续在左子树查找删除该结点
            root.left = deleteNode(root.left, key);
        } else {  //如果找到了该结点，删除它
            if(root.left == null && root.right == null) {  //以叶子节点为根节点的二叉搜索树只有一个元素，可以直接删除
                root = null;
            } else if(root.right != null) {  //如果有右子树，只要找到该右子树的后继节点来替换，之后将其删除即可
                root.val = successor(root);
                root.right = deleteNode(root.right, root.val);
            } else {  //如果有左子树，只要找到前驱节点来替换，然后将其删除即可
                root.val = predecessor(root);
                root.left = deleteNode(root.left, root.val);
            }
        }
        return root;
    }
}