Python怎么實現(xiàn)二叉樹按層級遍歷

這篇文章主要講解了“Python怎么實現(xiàn)二叉樹按層級遍歷”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“Python怎么實現(xiàn)二叉樹按層級遍歷”吧！

Python實現(xiàn)二叉樹按層級遍歷，看起來有點復(fù)雜。如下圖，如果一個二叉樹有多層，則從上到下，每層按從左到右遍歷。

每層放在一個隊列，整體返回一個多組隊列的隊列。

看起來復(fù)雜，其實實現(xiàn)反而很簡單；不用棧，就用一個節(jié)點隊列放當(dāng)前層級節(jié)點，遍歷當(dāng)前層級節(jié)點，讀取值放入一個讀取隊列，讀取當(dāng)前節(jié)點的子節(jié)點放入另一個隊列；當(dāng)當(dāng)前隊列節(jié)點遍歷完成后，使用下一層節(jié)點對用，相當(dāng)于進(jìn)入下一層，遍歷剛剛生成子節(jié)點隊列，如此反復(fù)直到節(jié)點隊列為空結(jié)束。

代碼如下

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        traversalList = []
        nodeList = []
        if root != None:
            nodeList.append(root)
            while nodeList != []:
                currentLevelVal = []
                currentNodeList = []
                for node in nodeList:
                    currentLevelVal.append(node.val)
                    if node.left != None:
                        currentNodeList.append(node.left)
                    if node.right != None:
                        currentNodeList.append(node.right)
                traversalList.append(currentLevelVal)
                nodeList = currentNodeList
        return traversalList

感謝各位的閱讀，以上就是“Python怎么實現(xiàn)二叉樹按層級遍歷”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對Python怎么實現(xiàn)二叉樹按層級遍歷這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！