基本上一棵不是二叉树的树可以按两个顺序遍历：前序（在挂在它的子树之前枚举内部节点）和后序（在挂在它的子树之后枚举内部节点）。我猜想在您的问题中，“自下而上”是后购，而“自上而下”是预购。
让我们进一步假设所有对象都可以相互分离，即它们具有不同的值或指针。如果所有对象都是相同的，即都是相同的状态，则不能仅从遍历列表中推断出树的形状，因为它们看起来相同。
现在的问题是，如果有一棵树 T，并且前序和后序遍历为其生成节点列表，则该树的根是前序列表上的 FIRST 节点和后序列表上的最后一个节点。这为您提供了以下重建方法：
您有两个列表，前序和后序遍历节点列表。将这些称为 R (pRe) 和 O (pOst)。
- R 的第一个元素是根节点。从 R 中删除它
- 从 O 中删除最后一个元素并检查它是否是同一个根节点（应该是）
- 现在检查 R 的第一个元素，它是最左边子树的根
- 从O中找到相同的节点；假设它是O 上的第k个节点
- 现在最左边的子树上有k个节点；从列表 R 和 O 中取出前k个节点并递归执行此算法以重建最左边的子树
- 继续R和O的剩余部分，迭代这个，重构根节点的剩余子树
伪代码 - 返回树的递归过程。输入：两个遍历列表 r = preorder, o = postorder
def mktree(r, o):
l = len(r)
assert l == len(o)
root = r[0]
assert root == o[l - 1]
if l == 1:
return mknode(root)
else:
myroot = mknode(root)
r = r[1:l] # sublist that excludes first element
o = o[0:l-1] # sublist that excludes last element
while len(r) > 0: # iterate and construct subtrees
first = r[0]
lim = -1
for i in 0..l - 1:
if o[i] == first:
lim = i + 1
break
assert lim != -1
myroot.add_rightmost_child(mktree(r[0:lim], o[0:lim])
r = r[lim:len(r)] # sublist from lim until end of list
o = o[lim:len(o)] # sublist from lim until end of list
return myroot
这是它如何工作的示例：
原始树：
1
/ | \
2 3 4
/ / \
5 6 7
前序遍历（“自上而下的深度优先”）：1 2 5 3 4 6 7
后序遍历（“自下而上”）：5 2 3 6 7 4 1
算法执行：
mktree(1253467, 5236741)
myroot = 1
r = 253467, o = 523674
loc = 1 (location of '2' in o)
mktree(25, 52)
myroot = 2
mktree(5, 5) -> returns singleton tree 5
list exhausted -> returns tree 2[5] (5 only child of 2)
add 2[5] to myroot as right child, tree at myroot 1[2[5]]
r = 3467, o = 3674 (stripped away "25" that was processed)
loc = 0 (location of '3' in o)
mktree(3, 3) returns singleton tree 3
add 3 to myroot as right child, tree at myroot 1[2[5], 3]
r = 467, o = 674 (stripped away "3" that was processed)
loc = 2 (location of '4' in o)
mktree(467, 674)
myroot = 4
r = 67, o = 67
(recursive calls return first singleton 6, then 7)
returns tree 4[6,7]
add 4[6,7] to myroot as right child, tree at myroot 1[2[5],3,4[6,7]]
list exhausted, return tree
结果，重建了原始树。
作为参考，这里定义了伪代码中的前序和后序遍历：
def preorder(t):
l = [root_node(t)] # BEFORE recursion = PREorder
for c in t.children(): # in left to right order
l.append(preorder(c))
return l
def postorder(t):
l = []
for c in t.children(): # in left to right order
l.append(postorder(c))
l.append(root_node(t)) # AFTER recursion = POSTorder
return l