给定一个树的遍历顺序，找出它是前序中序还是后序

Question

假设有人给我一个从 A 到 G 的节点的树遍历顺序 - F, B, A, D, C, E, G, I, H，可以是前序、中序或后序

1. 如何高效判断是前序、中序还是后序？
2. 如何有效地重建树，而不必为三种遍历类型中的每一种构建树，如下所示？

Answer 1

假设给你的树遍历是准确的--

如果你没有任何关于“什么样的树”的信息，你就无法知道它是什么类型的遍历。

如果您获得有关树以及值如何组织的信息，您可能可以。

如果是二叉树，并且如果：

• 列表是完美排序的，绝对是按顺序的

• 列表没有排序，并且列表中不是最小值的某个值是第一个值， 它肯定是预先订购的（第一个值是根）

• 列表未排序，第一个值是最小值。这绝对是后序的。

考虑到二叉树的遍历，

如果是有序的：有不止一棵树会导致有序遍历。

如果是预序的：正好有一个树与其对应（列表中的第一个总是该子树的根，小于根的值在左子树中，大于的值在右子树中）

如果后序：恰好是一个子树（类似于上面的预序。）

Answer 2

二叉树节点

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

按根将树拆分为左右子树（pre[0]）

def split_tree(pre, ino):
    l_ino, l_pre, r_ino, r_pre = None, None, None, None
    iri = None # in-order root index

    for i in range(len(ino)):
        if ino[i] == pre[0]:
            iri = ino[i-1]
            l_ino = ino[:i]
            r_ino = ino[i+1:]
            break
    for i in range(len(pre)):
        if iri == pre[i]:
            r_pre = pre[i+1:]
            l_pre = pre[1:i+1]
            break

    return (l_ino, l_pre, r_ino, r_pre)

构造二叉树

通过获取预序和中序遍历列表

def construct_bt(pre, ino):
    if len(ino) != len(pre):
        print('Error ino and pre is not match')
        return 
    
    if len(ino) == 0:
        return
    
    l_ino, l_pre, r_ino, r_pre = split_tree(pre, ino)

    root = BTNode(pre[0])
    root.left = construct_bt(l_pre, l_ino)
    root.right = construct_bt(r_pre, r_ino)

    return root

预序和中序遍历示例

pre = [1, 2, 4, 8, 9, 10, 11, 5, 3, 6, 7]
ino = [8, 4, 10, 9, 11, 2, 5, 1, 6, 3, 7]

# root of binary tree 
root = construct_bt(pre, ino)