【算法模板】二叉树节点删除

例题：删除二叉搜索树中的节点

以力扣面试题 450题为例：

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

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

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

// 深搜遍历本身不是难事，重要的是如何保持节点删除后，顶层树和子树的拼接
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;
        }
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        }
		// 找到删除的节点
        if (root.val == key) {
            if (root.left == null && root.right == null) {
                return null;
            }
            if (root.right == null) {
                return root.left;
            }
            if (root.left == null) {
                return root.right;
            }
			// 套路：删除的节点都有左右子树，那么就找到右子树的最小节点
			// 这个最小节点可以建立一个新的子树：即它的左子树是删除节点的左子树（最小节点正好是删除节点右子树中，大于删除节点左子树的最小值）；同时它的右子树可以是“去除了当前这个最小节点的删除节点右子树”（去除后的删除节点右子树所有节点值都大于最小节点）。
			// 那么最小节点可以替代删除节点，拼接回顶层树。
			
			// 1. 找到最小节点
            TreeNode successor = root.right;
            while (successor.left != null) {
                successor = successor.left;
            }
			
			// 2. 去除了当前这个最小节点的删除节点右子树
            root.right = deleteNode(root.right, successor.val);
			
			// 3. 建立一个新的子树，拼接回顶层树
            successor.right = root.right;
            successor.left = root.left;
            return successor;
        }
        return root;
    }
}