Настройте функцию построения ()

Изменения:

• Используйте имя переменной, например lookup, чтобы не затмевать имя существующего типа (например, dict).
• Go from right to left
  • Start from the end
  • Уменьшайте pIndex по пути
  • Обновить pIndex с противоположного направления

def construct_post(start, end, postorder, pIndex, lookup):
    # base case
    if start > end or pIndex < 0:
        return None, pIndex
 
    root = Node(postorder[pIndex])
    
    # go from the right to the left instead
    pIndex = pIndex - 1

    index = lookup[root.data]

    # update pIndex going in the opposite direction
    root.right, pIndex = construct_post(index + 1, end, postorder, pIndex, lookup)
    root.left, pIndex = construct_post(start, index - 1, postorder, pIndex, lookup)

    return root, pIndex


def constructTree_post(inorder, postorder):
    lookup = {e: i for i, e in enumerate(inorder)}
    pIndex = len(postorder) - 1

    # start from the end
    return construct_post(0, len(inorder) - 1, postorder, pIndex, lookup)[0]

Получившееся дерево:

          1
       /     \
     2        3
   /        /   \
  4        5     6
          / \
         7   8

Даже не читая страницы Geeks-for-Geeks, я решил реализовать свои собственные алгоритмы построения функций (preorder-postorder, preorder-inorder, inorder-postorder).

Все мои алгоритмы O(N^2) сложности.

Помимо функций построения (construct_preorder_postorder(), construct_preorder_inorder(), construct_inorder_postorder()) я также реализовал функции обхода (traverse_preorder(), traverse_inorder(), traverse_postorder()), функцию печати дерева консоли (print_tree()) и функцию сравнения равенства узлов (__eq__()).

Попробуйте онлайн!

class Node:
    def __init__(self, data, left = None, right = None):
        self.data = data
        self.left = left
        self.right = right
    def __eq__(self, other):
        return (self.data == other.data and self.left == other.left and
            self.right == other.right)
        
def traverse_inorder(node):
    return ([] if node is None else
        traverse_inorder(node.left) + [node.data] + traverse_inorder(node.right))
        
def traverse_preorder(node):
    return ([] if node is None else
        [node.data] + traverse_preorder(node.left) + traverse_preorder(node.right))
        
def traverse_postorder(node):
    return ([] if node is None else
        traverse_postorder(node.left) + traverse_postorder(node.right) + [node.data])
        
def construct_preorder_postorder(pre, post):
    assert sorted(pre) == sorted(post) and len(pre) == len(set(pre)), (pre, post)
    if len(pre) == 0:
        return None
    if len(pre) == 1:
        return Node(pre[0])
    root, l = pre[0], pre[1]
    for i, e in enumerate(post):
        if e == l:
            ls = i + 1
            rs = len(post) - 1 - ls
            break
    return Node(root,
        None if ls == 0 else construct_preorder_postorder(pre[1:1 + ls], post[:ls]),
        None if rs == 0 else construct_preorder_postorder(pre[-rs:], post[-1 - rs:-1]))
        
def construct_preorder_inorder(pre, ino):
    assert sorted(pre) == sorted(ino) and len(pre) == len(set(pre)), (pre, ino)
    if len(pre) == 0:
        return None
    if len(pre) == 1:
        return Node(pre[0])
    root, l = pre[0], pre[1]
    for i, e in enumerate(ino):
        if e == root:
            ls = i
            rs = len(ino) - 1 - ls
            break
    return Node(root,
        None if ls == 0 else construct_preorder_inorder(pre[1:1 + ls], ino[:ls]),
        None if rs == 0 else construct_preorder_inorder(pre[-rs:], ino[-rs:]))
        
def construct_inorder_postorder(ino, post):
    assert sorted(ino) == sorted(post) and len(ino) == len(set(ino)), (ino, post)
    if len(post) == 0:
        return None
    if len(post) == 1:
        return Node(post[0])
    root, r = post[-1], post[-2]
    for i, e in enumerate(ino):
        if e == root:
            ls = i
            rs = len(ino) - 1 - ls
            break
    return Node(root,
        None if ls == 0 else construct_inorder_postorder(ino[:ls], post[:ls]),
        None if rs == 0 else construct_inorder_postorder(ino[-rs:], post[-1 - rs:-1]))
    
def print_tree(node):
    def inner(node, *, upref = '', cpref = '', dpref = ''):
        if node is None:
            return
        inner(node.right, upref = dpref + '  |',
            cpref = dpref + '  /', dpref = dpref + '   ')
        print(cpref + '--' + str(node.data))
        inner(node.left, upref = upref + '   ',
            cpref = upref + '  \\', dpref = upref + '  |')
    inner(node)
        
if __name__ == '__main__':
    node = Node(1, Node(2, Node(4)), Node(3, Node(5, Node(7), Node(8)), Node(6)))
    print_tree(node)
    preorder, inorder, postorder = (
        traverse_preorder(node), traverse_inorder(node), traverse_postorder(node))
    preorder_cons, inorder_cons, postorder_cons = (
        construct_preorder_postorder(preorder, postorder),
        construct_preorder_inorder(preorder, inorder),
        construct_inorder_postorder(inorder, postorder),
    )
    assert preorder_cons == inorder_cons == postorder_cons

Выход:

     /--6
  /--3
  |  |  /--8
  |  \--5
  |     \--7
--1
  \--2
     \--4