450. Delete Node in a BST.md

450. Delete Node in a BST

https://leetcode.com/problems/delete-node-in-a-bst/

solution

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

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()

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

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

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

普通二叉树的删除方式

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

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