Построение бинарного дерева из обхода по порядку и порядку

Question

Я пытаюсь построить двоичное дерево из обхода по порядку и порядку.Я считаю, что рекурсивная часть верна, но я не уверен насчет базовых случаев.Любые указатели приветствуются.

Я пробовал разные комбинации базовых сценариев, но я не могу заставить их работать.

class BinaryTreeNode:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


def binary_tree_from_postorder_inorder(postorder, inorder):
    node_to_inorder_idx = {data: i for i, data in enumerate(inorder)}


    def helper(
        postorder_start, postorder_end, inorder_start, inorder_end
    ):
        if postorder_end >= postorder_start or inorder_end <= inorder_start:
            return None


        root_inorder_idx = node_to_inorder_idx[postorder[postorder_start]]
        left_subtree_size = root_inorder_idx - inorder_start

        root = BinaryTreeNode(postorder[postorder_start])

        root.right = helper(
            postorder_start - 1,
            postorder_start - 1 - left_subtree_size,
            root_inorder_idx + 1,
            inorder_end,
        )
        root.left = helper(
            postorder_start - 1 - left_subtree_size,
            postorder_end,
            inorder_start,
            root_inorder_idx,
        )

        return root

     return helper(len(postorder) - 1, -1, 0, len(inorder))

def inorder(tree):
    stack = []
    results = []

    while stack or tree:
        if tree:
            stack.append(tree)
            tree = tree.left
        else:
            tree = stack.pop()
            results.append(tree.data)
            tree = tree.right
    return results


inorder = ["F", "B", "A", "E", "H", "C", "D", "I", "G"]
postorder = ["F", "A", "E", "B", "I", "G", "D", "C", "H"]

root_pos_in = binary_tree_from_postorder_inorder(postorder, inorder)

print(inorder(root_pos_in))

Входные данные:

inorder = ["F", "B", "A", "E", "H", "C", "D", "I", "G"]
postorder = ["F", "A", "E", "B", "I", "G", "D", "C", "H"]

Фактический результат с использованием обхода по порядку: ["A", "B", "E", "H", "C"]

Ожидаемый результат: ["F", "B", "A", "E", "H", "C", "D", "I", "G"]

Answer 1

Прошло много времени с тех пор, как я имел дело с Python, но это выглядит как большой код для того, что кажется простым алгоритмом.

Вот пример применения алгоритма:

Начнем с

postorder  |  inorder
-----------|----------
           |               
FAEBIGDCH  | FBAEHCDIG
        ^  |
        |  |
         `-+-------------- last value of postorder: 'H': this is the root value
           |               
FAEBIGDCH  | FBAEHCDIG
           |     ^
           |     |
           |      `------- index of 'H' in inorder: 4
           |               
FAEB_....  | FBAE_....
  ^        |   ^
  |        |   |
  |        |    `--------- everything before index 4
  |        |
   `-------+-------------- everything before index 4
           |               
....IGDC_  | ...._CDIG
      ^    |        ^ 
      |    |        |
      |    |         `---- everything beginning with index 5 (4 + 1)
      |    |
       `---+-------------- everything between index 4 and the 'H' at the end
           |               
FAEB       | FBAE
  ^        |   ^
  |        |   |
   `-------+---+---------- recur on these if not empty: this is the left child
           |               
     IGDC  |      CDIG
       ^   |        ^
       |   |        |
        `--+--------+----- recur on these if not empty: this is the right child

Это быстро приведет нас к дереву, как

               H
               |
      +--------+--------+
      |                 |
      B                 C
      |                 |
+-----+-----+           +-----+
|           |                 |
F           E                 D
            |                 |
        +---+                 +---+
        |                         |
        A                         G
                                +-+
                                |
                                I

Так что, хотя я не могу реально критиковать ваш Python, я могу предложить довольно простую версию JS:

const makeTree = (
    postord, inord, 
    len = postord.length, val = postord[len - 1], idx = inord.indexOf(val)
  ) =>
    len == 1
      ? {val}
    : {
        val,
        ...(idx > 0 ? {left: makeTree(postord.slice(0, idx), inord.slice(0, idx))} : {}),
        ...(idx < len - 1 ? {right: makeTree(postord.slice(idx, len - 1), inord.slice(idx + 1, len))} : {})
      }

const postOrder = ["F", "A", "E", "B", "I", "G", "D", "C", "H"]
const inOrder =   ["F", "B", "A", "E", "H", "C", "D", "I", "G"]

console .log (
  makeTree (postOrder, inOrder)
)

Answer 2

Поработав немного дольше, я смог решить проблему.Смотрите мою обновленную функцию ниже:

def binary_tree_from_postorder_inorder(postorder, inorder):
    if not inorder or not postorder or len(postorder) != len(inorder):
        return None

    node_to_inorder_idx = {data: i for i, data in enumerate(inorder)}

    def helper(postorder_start, postorder_end, inorder_start, inorder_end):
        if postorder_start > postorder_end or inorder_start > inorder_end:
            return None

        root_index = node_to_inorder_idx[postorder[postorder_end]]
        left_subtree_size = root_index - inorder_start

        return BinaryTreeNode(
            postorder[postorder_end],
            helper(
                postorder_start,
                postorder_start + left_subtree_size - 1,
                inorder_start,
                root_index - 1,
            ),
            helper(
                postorder_start + left_subtree_size,
                postorder_end - 1,
                root_index + 1,
                inorder_end,
            ),
        )

    return helper(0, len(postorder) - 1, 0, len(inorder) - 1)