Introduction

In this blog post, we will explore how to solve the LeetCode problem "1028" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

We run a preorder depth-first search (DFS) on the root of a binary tree. At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. If the depth of a node is D, the depth of its immediate child is D + 1. The depth of the root node is 0. If a node has only one child, that child is guaranteed to be the left child. Given the output traversal of this traversal, recover the tree and return its root. Example 1: Input: traversal = "1-2--3--4-5--6--7" Output: [1,2,5,3,4,6,7] Example 2: Input: traversal = "1-2--3---4-5--6---7" Output: [1,2,5,3,null,6,null,4,null,7] Example 3: Input: traversal = "1-401--349---90--88" Output: [1,401,null,349,88,90] Constraints: The number of nodes in the original tree is in the range [1, 1000]. 1 <= Node.val <= 109

Explanation

Here's a breakdown of the solution:

• Utilize Depth Information: The number of dashes preceding a node's value directly corresponds to its depth in the tree. This is key to reconstructing the tree structure.
• Iterative Tree Construction: Process the traversal string sequentially. For each node encountered, determine its depth and value. Then, find the correct parent node at the preceding depth to attach the new node to.

• Stack for Parent Tracking: Maintain a stack to keep track of the nodes at each depth. As we process the traversal, we can easily access the potential parents using the stack.

• Runtime & Storage Complexity: O(N) runtime complexity, where N is the length of the traversal string. O(H) storage complexity, where H is the height of the binary tree, due to the stack. In the worst case, H can be equal to N.

Code

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

def recoverFromPreorder(traversal: str) -> TreeNode:
    """
    Recovers a binary tree from its preorder traversal string.
    """

    stack = []
    i = 0
    while i < len(traversal):
        depth = 0
        while i < len(traversal) and traversal[i] == '-':
            depth += 1
            i += 1

        val = 0
        while i < len(traversal) and traversal[i].isdigit():
            val = val * 10 + int(traversal[i])
            i += 1

        node = TreeNode(val)

        while len(stack) > depth:
            stack.pop()

        if not stack:
            root = node
            stack.append(node)
        else:
            parent = stack[-1]
            if not parent.left:
                parent.left = node
            else:
                parent.right = node
            stack.append(node)

    return root