ConstructBinaryTreeFromPreorderAndInorderTraversal

Problem

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Solution

Since preorder traversal prints the root node first, we extract the value val of the root node from the tip of preorder. The same value val divides inorder into two parts: the left subtree and the right subtree. We can then recursively build the left subtree by using the rest of the preorder and the left half of inorder. Once the left subtree is built, we build the right subtree by using the rest of the preorder from buliding the left subtree and the right half of inorder.

Code

>>> addTwoNumbers(l1, l2).to_list()
[8, 9, 9, 9, 0, 0, 0, 1]
"""



class ListNode:
    """Node in a linked list.
    """

    def __init__(self, val: int, next: ListNode | None = None):
        self.val = val
        self.next = next

    def to_list(self):
        list = []
        while self is not None:
            list.append(self.val)
            self = self.next
        return list

    @classmethod
    def from_list(cls, list: ListNode[int]) -> ListNode | None:
        head: ListNode | None = None
        for el in list:
            if head is None:
                head = ListNode(el)
                node = head
            else:
                node.next = ListNode(el)
                node = node.next
        return head


def addTwoNumbers(l1: ListNode | None, l2: ListNode | None):
    """Add two numbers whose digits are stored in little endian linked lists.
    """
    head = None

    carry = 0
    while not (l1 is None and l2 is None and carry == 0):
        if l1 is not None:
            val1 = l1.val
            l1 = l1.next
        else:
            val1 = 0

        if l2 is not None:
            val2 = l2.val
            l2 = l2.next
        else:
            val2 = 0

        s = carry + val1 + val2
        digit = s % 10
        carry = s // 10

        if head is None:
            head = ListNode(digit, None)
            node = head
        else:
            node.next = ListNode(digit, None)
            node = node.next

    return head

Test

>>> from ConstructBinaryTreeFromPreorderAndInorderTraversal import buildTree
>>> preorder = [3, 9, 20, 15, 7]
>>> inorder = [9, 3, 15, 20, 7]
>>> root = buildTree(preorder, inorder)
>>> root.preorder()
[3, 9, 20, 15, 7]
>>> root.inorder()
[9, 3, 15, 20, 7]
>>> preorder = [-1]
>>> inorder = [-1]
>>> root = buildTree(preorder, inorder)
>>> root.preorder()
[-1]
>>> root.inorder()
[-1]

class ConstructBinaryTreeFromPreorderAndInorderTraversal.TreeNode(val, left=None, right=None)

Bases: object

Node in a binary tree.

inorder()

preorder()

ConstructBinaryTreeFromPreorderAndInorderTraversal.buildTree(preorder: List[int], inorder: List[int]) → TreeNode | None

Build a binary tree from its preorder and inorder traversals.

ConstructBinaryTreeFromPreorderAndInorderTraversal.build_tree(preorder: List[int], inorder: List[int]) → Tuple[TreeNode | None, List[int]]

Recursively build a binary tree from part of its preorder and inorder traversals.