# 450. Delete Node in a BST

[https://leetcode.com/problems/delete-node-in-a-bst/](https://leetcode.com/problems/delete-node-in-a-bst/)

## solution

* 二叉树返回的是新的节点，为了让删除后的节点接到新节点上，采用后续遍历
* 注意return位置，递归中的返回以及整体函数的结果返回

```python
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None

        if root.val < key:
            root.right = self.deleteNode(root.right, key)
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        else:
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            else:
                node = root.right
                while node.left:
                    node = node.left
                node.left = root.left
                root = root.right
        return root
```

时间复杂度：O()\
空间复杂度：O()

```python
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if root is None:
            return None

        if root.val == key:
            if root.left is None and root.right is None:  # 一开始漏了这里的条件
                return None
            if root.left is None and root.right is not None:
                return root.right
            if root.right is None and root.left is not None:
                return root.left
            if root.right is not None and root.left is not None:
                cur = root.right
                while cur.left is not None:
                    cur = cur.left
                cur.left = root.left
                return root.right

        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        if root.val < key:
            root.right = self.deleteNode(root.right, key)
        return root
```

## follow up

[701. Insert into a Binary Search Tree](https://leetcode.com/problems/insert-into-a-binary-search-tree/)

* 思路非常重要，容易自己绕晕
* 通过递归函数的返回值完成父子节点的赋值。函数执行完毕后会将返回值赋值给此变量，递归函数中，第三层递归的返回值给第二层.第二层的给第一层.第一层的给主函数

```python
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None:
            return TreeNode(val)

        if root.val < val:
            root.right = self.insertIntoBST(root.right, val)
        if root.val > val:
            root.left = self.insertIntoBST(root.left, val)
        return root
```

时间复杂度：O()\
空间复杂度：O()

[669 Trim a Binary Search Tree](669.-trim-a-binary-search-tree)

[普通二叉树的删除方式](450.-delete-node-in-a-bst)

\[Given a binary tree, how do you remove all the half nodes?]

```python
def RemoveHalfNodes(root):
    if root is None:
        return None

    root.left = RemoveHalfNodes(root.left)
    root.right = RemoveHalfNodes(root.right)

    # if both left and right child is None
    # the node is not a Half node
    if root.left is None and root.right is None:
        return root

    # If current nodes is a half node with left child
    # None then it's right child is returned and
    # replaces it in the given tree
    if root.left is None:
        new_root = root.right
        temp = root
        root = None
        del(temp)
        return new_root

    if root.right is None:
        new_root = root.left
        temp = root
        root = None
        del(temp)
        return new_root

    return root
```
