Constraints

• Let `L` be the number of nodes in the list.
• `1 <= L <= 10^5`
• `1 <= n <= L`
• Node values are integers in the range `[-10^9, 10^9]`

Examples

Solution

def solution(head, n):
    class ListNode:
        __slots__ = ("val", "next")

        def __init__(self, val=0, next=None):
            self.val = val
            self.next = next

    def build(encoded):
        dummy = ListNode()
        cur = dummy
        while encoded is not None:
            val, encoded = encoded
            cur.next = ListNode(val)
            cur = cur.next
        return dummy.next

    def encode(node):
        values = []
        while node is not None:
            values.append(node.val)
            node = node.next

        encoded = None
        for value in reversed(values):
            encoded = (value, encoded)
        return encoded

    if head is None:
        return None

    linked_head = build(head)
    dummy = ListNode(0, linked_head)
    fast = dummy
    slow = dummy

    for _ in range(n):
        fast = fast.next

    while fast.next is not None:
        fast = fast.next
        slow = slow.next

    slow.next = slow.next.next
    return encode(dummy.next)

Time complexity: O(L). Space complexity: O(L) due to converting between the tuple encoding and linked-list nodes. The core two-pointer deletion step itself uses O(1) extra space..

Hints

1. A dummy node before the head makes deleting the first real node much easier.
2. Use two pointers: move one pointer `n` steps ahead, then move both pointers together until the front pointer reaches the end.

Constraints

• `0 <= N <= 10^4`, where `N` is the number of non-`None` nodes in the tree
• Tree values are integers in the range `[-10^9, 10^9]`
• The tree is not necessarily a BST
• An `O(N)` time solution is expected
• `O(N)` auxiliary space is allowed

Examples

Solution

def solution(root, key):
    from collections import deque

    class TreeNode:
        __slots__ = ("val", "left", "right")

        def __init__(self, val=0, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right

    def build(levels):
        if not levels or levels[0] is None:
            return None

        root_node = TreeNode(levels[0])
        queue = deque([root_node])
        i = 1

        while queue and i < len(levels):
            node = queue.popleft()

            if i < len(levels):
                left_val = levels[i]
                i += 1
                if left_val is not None:
                    node.left = TreeNode(left_val)
                    queue.append(node.left)

            if i < len(levels):
                right_val = levels[i]
                i += 1
                if right_val is not None:
                    node.right = TreeNode(right_val)
                    queue.append(node.right)

        return root_node

    def serialize(root_node):
        if root_node is None:
            return []

        result = []
        queue = deque([root_node])

        while queue:
            node = queue.popleft()
            if node is None:
                result.append(None)
            else:
                result.append(node.val)
                queue.append(node.left)
                queue.append(node.right)

        while result and result[-1] is None:
            result.pop()

        return result

    root_node = build(root)
    if root_node is None:
        return []

    queue = deque([(root_node, None)])
    target = None
    deepest = None
    deepest_parent = None

    while queue:
        node, parent = queue.popleft()

        if target is None and node.val == key:
            target = node

        deepest = node
        deepest_parent = parent

        if node.left is not None:
            queue.append((node.left, node))
        if node.right is not None:
            queue.append((node.right, node))

    if target is None:
        return serialize(root_node)

    if deepest_parent is None and target is root_node:
        return []

    target.val = deepest.val

    if deepest_parent.left is deepest:
        deepest_parent.left = None
    else:
        deepest_parent.right = None

    return serialize(root_node)

Time complexity: O(N). Space complexity: O(N).

Hints

1. A breadth-first search can simultaneously find the target node, the deepest-rightmost node, and each node's parent.
2. After replacing the target value, be careful to delete the original deepest-rightmost node from its parent, not the target node itself.