algorithm - 在不构造二叉树的情况下进行后序到前序的转换

Question

我得到了postorder和inorder。我的任务是打印预购，但我无法构造二叉树。

示例：在：POSTORDER 4 2 7 5 9 8 6 3 1 INORDER 4 2 1 5 7 3 6 8 9

输出：1 2 4 3 5 7 6 8 9

谁能帮我解决这个问题？

Answer 1

知道了....

这里要理解的关键观察是：

1）后序数组的最后一个值是给定树的根。

2）要找到应该去左子树和右子树的值，找到我们的根（即后序数组中的最后一个值）在中序数组中的索引。中序数组中该索引左侧的所有值都属于左子树，该索引右侧的所有值都属于右子树。好？

因此，从上面的示例中，整个树的根为 1。在中序数组中，1 的索引为 2。因此，对于左子树：

后序 = [4,2]，序序 = [4,2]

对于右子树：Postorder = [ 7, 5, 9, 8, 6, 3], inorder = [5, 7, 3, 6, 8, 9]

而已。递归会处理剩下的事情。

我在 Pyhton 中的示例代码 -

post = [4, 2, 7, 5, 9, 8, 6, 3, 1]
inor = [4, 2, 1, 5, 7, 3, 6, 8, 9]

class Node:
    def __init__(self,v):
        self.v = v
        self.l = None
        self.r = None

def build(post,inor):
    assert len(post)==len(inor)
    if not post:
        return None

    root = Node(post[-1])
    if len(post)==1:
        return root

    for i in range(len(inor)): #finding index of root in inorder, in i
        if inor[i] == root.v:
            break

    root.l = build(post[:i],inor[:i]) #both arrays from 0 to index i
    root.r = build(post[i:-1],inor[i+1:]) #post skips last value, which is root
    return root

def pre(r):
    if r==None:return

    print(r.v)
    pre(r.l)
    pre(r.r)

r = build(post,inor)
pre(r)