不构造二叉树的后序Inorder到Preorder的转换

Question

我已经收到了后序和中序。我的任务是打印预购，但是我无法构造二叉树

示例：在：海报 4 2 7 5 9 8 6 3 1 为了 4 2 1 5 7 3 6 8 9

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

谁能帮我解决这个问题？

Answer 1

知道了....

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

1) post-order 数组的最后一个值是给定树的根。

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

所以，从上面的例子来看，整棵树的根是1。在中序数组中，1的索引是2。所以，对于左子树：

postorder = [4,2], Inorder = [4,2]

对于右子树：后序 = [ 7, 5, 9, 8, 6, 3], 中序 = [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)

不构造二叉树的后序Inorder到Preorder的转换

Postorder Inorder to Preorder conversion without constructing Binary Tree

algorithm

binary-tree

inorder

preorder

postorder