# 0450. Delete Node in a BST
###### tags: `Leetcode` `Medium` `DFS`
Link: https://leetcode.com/problems/delete-node-in-a-bst/
## 思路 $O(logN)$ $O(H)$
首先注意条件是binary search tree
遇到一个需要删除的node
- 首先看他有没有child，如果没有，直接删除即可
- 如果右边非空，则找右边最小的node（通过successor function），来替换掉这个需要被删除的node，接下来再通过递回，把这个替换的node删除
- 如果右边为空，左边非空，则找左边最大的node（通过predecessor function），来替换这个需要被删除的node，接下来再通过递归，把这个替换的node删除
## Code

class Solution {
    private int successor(TreeNode root){
        root = root.right;
        while(root.left!=null) root = root.left;
        return root.val;
    }
    private 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(root.val < key){
            root.right = deleteNode(root.right, key);
        }
        else if(root.val > key){
            root.left = deleteNode(root.left, key);
        }
        else{
            if(root.left == null && root.right == null) return 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;
    }
}