首页 > 试题广场 >

问题:手撕代码,根据前序,中序创建二叉树。

[问答题]

问题:手撕代码,根据前序,中序创建二叉树。

def buildBTreeFromPreIn(preo, ino):
    if (preo == '' or ino == ''):
        return None
    pos = ino.find(preo[0])  # 在中序遍历中,找到根节点,从而可左右划分出左右子树
    if (pos < 0):
        return None
    # 前序: 父左右  中序: 左父右
    return BTree(preo[0], buildBTreeFromPreIn(preo[1:pos + 1], ino[0:pos]), # 迭代的找,前序的根节点,在中序中的位置,迭代重构出树
                 buildBTreeFromPreIn(preo[pos + 1:], ino[pos + 1:]))

发表于 2019-07-18 21:20:19 回复(0)