使用字典vs隊列的Python級別的命令遍歷

我對Algo & DS的理解有點新手。而且我不確定這是否是重複或相關問題，或者是否完全無關緊要。無論我在哪裏看到級別遍歷或BFS被提及，我都會看到使用了隊列。我無法理解錯綜複雜的空間，更重要的是時間複雜度,對我的實現使用字典。使用字典vs隊列的Python級別的命令遍歷

def getLevelElements(tree, level=0, cont={}): 
    """Get mapping of level and elements in a level 
    :param tree: Input tree, ex. 
     1 
      2 
       4 
       5 
        8 
        9 
      3 
       6 
       7 
        10 
        None 
    :return: {0: [1], 1: [2, 3], 2: [4, 5, 6, 7], 3: [8, 9, 10]} 
    """ 
    if tree is not None: 
     cont.setdefault(level, []).append(tree.root) 
    if tree.leftChild is not None: 
     getLevelElements(tree.leftChild, level + 1, cont) 
    if tree.rightChild is not None: 
     getLevelElements(tree.rightChild, level + 1, cont) 
    return cont 


def levelOrderTraversalOut(tree): 
    levelElementsMap = getLevelElements(tree) 
    out = [] 
    for elements in levelElementsMap.values(): 
     out += elements 
    return out

我的要求是使用級別遍歷在列表中獲取樹的元素。

來源

2016-11-18 Anshu Kumar

如果我理解你是對的，你需要樹的元素的BFS順序。我會建議像這樣的smth：

def bfs(tree): 
    out = [] 
    elements = [tree.root] 
    while elements: 
     elem = elements.pop(0) 
     out.append(elem) 
     if elem.leftChild: 
      elements.append(elem.leftChild) 
     if elem.rightChild: 
      elements.append(elem.rightChild) 
    return out

來源

2016-11-18 10:47:13

是的。雖然您是否也會幫助我瞭解解決方案的複雜性與我的解決方案 - 無論是時間還是空間？ –

是的。在這兩種解決方案中，樹中的每個元素只遍歷一次，因此它們具有線性時間複雜度。這兩個解決方案中的空間複雜性都是一樣的。 –

使用字典vs隊列的Python級別的命令遍歷

回答

相關問題