笔试算法题-day01

题目：给定一棵完全二叉树的层次遍历序列，以及树的结点数目，求解其先序遍历序列？
样例：输入为：ABCDE，5；输出：ABDEC
解题思路：主要考察了完全二叉树的特性（也即父节点与其儿子结点存在一个关系node_left=2*root+1,node_right=2*root+2），因此这里可以采用递归的解法；
def preorder(level_search,idx,n,preorder_list):
    if idx>n:
        return 
    else:
        preorder_list.append(level_search[idx])
        if 2*idx+1<n:
                preorder(level_search,2*idx+1,n,preorder_list)
        if 2*idx+2<n:
                preorder(level_search,2*idx+2,n,preorder_list)
if __name__=="__main__":
    input_="ABCDEF"
    n=len(input_)
    res=[]
    preorder(input_,0,n,res)
    print("".join(res))
        
考察知识点：完全二叉树的一些知识点，以及层次遍历（从上至下，从左至右）；