algorithm - 从有序和后序遍历构造二叉树

我试图从后序遍历和有序遍历构造一个二叉树。我相信递归部分是正确的，但我不确定基本情况任何指点都将不胜感激。
我尝试过不同的基本案例组合，但似乎无法奏效。

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"]

最佳答案

我处理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)
)