LeetCode Day 22 binary tree (8/9)

Day 8 of 9, go for it!

Question 1

235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

This question is similar to LC 236, and will be more clearly when using an iterative approach.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while True:
            if root.val > p.val and root.val > q.val:
                root = root.left
            elif root.val < p.val and root.val < q.val:
                root = root.right
            else:
                return root

Question 2

701. Insert into a Binary Search Tree

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

It can be traversed in accordance with the rules of the binary search tree, the empty nodes encountered on the insertion of nodes can be, as for how to traverse the binary tree, you can follow the recursive three-step operation.

Determine the parameters of the recursive function and the return value

• Parameter is the root node pointer, as well as to insert the element Return value, you can use the return value to complete the new node and its parent node assignment operation.The return type of the recursive function is the node type TreeNode *.

Determining the termination condition

• The termination condition is to find the traversal of the node is null when the position of the node to be inserted, and the insertion of the node to return.

Determine the logic of single-level recursion

• Search tree is a direction, can be based on the value of the inserted element, to determine the direction of recursion.

class Solution:
    def insertIntoBST(self, root, val):
        if root is None:
            return TreeNode(val)
        parent = None
        cur = root
        while cur:
            parent = cur
            if val < cur.val:
                cur = cur.left
            else:
                cur = cur.right
        if val < parent.val:
            parent.left = TreeNode(val)
        else:
            parent.right = TreeNode(val)
        return root

Question 3

450. Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

Deleting a node in the BST can have the following cases and is therefore more complicated than adding a node:

1. The first case: the deleted node is not found, and traversing to the empty node returns it directly
2. The deleted node is found
   1. Second case: the left and right children of the deleted node are empty (leaf nodes), the node is deleted directly, and NULL is returned as the root node.
   2. Third case: delete the left child of the node is empty, the right child is not empty, delete the node, the right child complement, return the right child for the root node
   3. The fourth case: the right child of the deleted node is empty, the left child is not empty, delete the node, the left child is complementary, return the left child to the root node.
   4. The fifth case: the left and right child nodes are not empty, then the left child of the deleted node is placed on the left child of the leftmost node of the deleted node’s right subtree, and the right child of the deleted node is returned as the new root node.

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if root is None:
            return root
        if root.val == key:
            if root.left is None and root.right is None:
                return None
            elif root.left is None:
                return root.right
            elif root.right is None:
                return root.left
            else:
                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