力扣---450. 删除二叉搜索树中的节点

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

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

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

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点
示例 3:

输入: root = [], key = 0
输出: []
 

提示:

节点数的范围 [0, 104].
-105 <= Node.val <= 105
节点值唯一
root 是合法的二叉搜索树
-105 <= key <= 105
 

进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/delete-node-in-a-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

麻烦的地方在于删除后继续保持二叉搜索树的性质。

class Solution {
    public TreeNode deleteNode (TreeNode root, int key) {
        if (root == null) {
            return null;
        }
//        对根结点进行判断，避开父节点为 null 的情况。
        if (root.val == key) {
            if (root.left == null && root.right == null) {
                return null;
            } else if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }
            getLeftLeaf(root.right).left = root.left;
            return root.right;
        } else {
            dfs(root, null, key, true);
        }
        return root;
    }
//    @direction 该节点为父节点的左子树还是右子树，true 为左，false 为右。
private void dfs (TreeNode root, TreeNode parent, int key, boolean direction) {
//        不包含 key
        if (root == null) {
            return;
        }
        if (root.val > key) {
            dfs(root.left, root, key, true);
        } else if (root.val < key) {
            dfs(root.right, root, key, false);
        } else {
//             找到 key 所在节点
//            第一种情况：目标节点的左右节点都为 null
            if (root.left == null && root.right == null) {
                if (direction) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
//            第二种情况：目标节点的左右节点都不为 null，此时将目标节点的左子树放到右子树最左边的叶子节点，然后将该节点删除即可（参考第三，第四种情况）。
            } else if (root.left != null && root.right != null) {
                getLeftLeaf(root.right).left = root.left;
                if (direction) {
                    parent.left = root.right;
                } else {
                    parent.right = root.right;
                }
//            第三种情况：目标节点的左节点为 null，此时将右子树直接替代目标节点即可。
            } else if (root.left == null) {
                if (direction) {
                    parent.left = root.right;
                } else {
                    parent.right = root.right;
                }
//            第四种情况：目标节点的右节点为 null，此时将左子树直接替代目标节点即可。
            } else {
                if (direction) {
                    parent.left = root.left;
                } else {
                    parent.right = root.left;
                }
            }

        }
    }

//    寻找目标节点右子树最左边的节点。
    private TreeNode getLeftLeaf (TreeNode root) {
        if (root.left == null) {
            return root;
        } else {
            return getLeftLeaf(root.left);
        }
    }
}