二叉樹(shù)的層序遍歷是如何實(shí)現(xiàn)的? 二叉樹(shù) 層遍歷
Noon日中優(yōu)選跨境問(wèn)答2025-08-066440
二叉樹(shù)的層序遍歷(Level Order Traversal)是指按照從上到下、從左到右的順序訪問(wèn)二叉樹(shù)的所有節(jié)點(diǎn)。在實(shí)現(xiàn)層序遍歷時(shí),需要使用隊(duì)列來(lái)存儲(chǔ)待訪問(wèn)的節(jié)點(diǎn),并按照層序依次訪問(wèn)。
以下是一個(gè)簡(jiǎn)單的 Python 實(shí)現(xiàn):
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def level_order_traversal(root):
if not root:
return []
queue = [root]
result = []
while queue:
level_size = len(queue)
for _ in range(level_size):
node = queue.pop(0)
result.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
這個(gè)實(shí)現(xiàn)中,我們首先定義了一個(gè) TreeNode
類(lèi)來(lái)表示二叉樹(shù)的節(jié)點(diǎn)。然后,我們定義了一個(gè) level_order_traversal
函數(shù)來(lái)實(shí)現(xiàn)層序遍歷。在這個(gè)函數(shù)中,我們使用一個(gè)隊(duì)列來(lái)存儲(chǔ)待訪問(wèn)的節(jié)點(diǎn),并按照層序依次訪問(wèn)。最后,訪問(wèn)到的節(jié)點(diǎn)值添加到結(jié)果列表中。
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理,出于傳遞更多信息之目的,不代表金鑰匙跨境贊同其觀點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明,如有侵權(quán),聯(lián)系刪除。