查找從它的前序遍歷序列中序遍歷二叉樹

Question

我給只有一個二叉樹的前序遍歷序列（例如{A，B，d，C，E}），任務是找到出從它的層序。請原諒我，如果這是一個重複的問題....感謝

Answer 1

我不認爲你可以找到僅基於序遍歷一個二叉樹序遍歷。當你爲二叉搜索樹表示，排序會給你序遍歷。

Answer 2

我已經準備Python中的函數從序遍歷得到序遍歷。也許這會幫助你希望。

例如，

如果你喜歡的輸入後序是 進入後序遍歷：ACEDBHIGF

預購會 的前序遍歷是GAECFTJOLP

的序將 的序遍歷是ABCDEFGHI

def from_post_order(post_order_items, order_type="pre"): 
    bst = BinarySearchTree() 
    values = [item for item in post_order_items] 
    root = values[-1] # the last item in the post_order item is ROOT 
    bst.insert(root) # insert ROOT 
    values.pop(-1) # and remove it from post_order_items 

    left_child = [] # the left child of ROOT for Post-order 
    right_child = [] # the right child of ROOT for Post-order 
    for v in values: 
     if v > root: 
      right_child.append(v) 
     else: 
      left_child.append(v) 

    for i in range(len(left_child + right_child)): 
     if len(left_child) != 0: 
      bst.insert(left_child[-1]) # insert left child 
      left_child.pop(-1) # remove the inserted left child from the list 

     if len(right_child) != 0: 
      bst.insert(right_child[-1]) # insert right child 
      right_child.pop(-1) # remove the inserted right child from the list 

    if order_type == "pre": 
     print("The pre-order traversal is ") 
     bst.preorder(print) 
    elif order_type == "in": 
     print("The in-order traversal is ") 
     bst.inorder(print) 
    else: 
     print("The post-order traversal is ") 
     bst.postorder(print)