如何實(shí)現(xiàn)TreeNode的遞歸遍歷

小樊
85
2024-09-03 12:03:10

要實(shí)現(xiàn)TreeNode的遞歸遍歷，你可以使用深度優(yōu)先搜索（DFS）或廣度優(yōu)先搜索（BFS）算法。這里我將分別介紹這兩種方法的實(shí)現(xiàn)。

首先，我們需要定義一個(gè)TreeNode類：

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []
  1. 深度優(yōu)先搜索（DFS）

使用遞歸實(shí)現(xiàn)深度優(yōu)先搜索：

def dfs_recursive(node):
    if node is None:
        return

    print(node.value)  # 處理當(dāng)前節(jié)點(diǎn)
    for child in node.children:
        dfs_recursive(child)  # 遞歸遍歷子節(jié)點(diǎn)
  1. 廣度優(yōu)先搜索（BFS）

使用隊(duì)列實(shí)現(xiàn)廣度優(yōu)先搜索：

from collections import deque

def bfs(root):
    if root is None:
        return

    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value)  # 處理當(dāng)前節(jié)點(diǎn)
        for child in node.children:
            queue.append(child)  # 將子節(jié)點(diǎn)加入隊(duì)列

以上代碼展示了如何實(shí)現(xiàn)TreeNode的遞歸遍歷。你可以根據(jù)需要選擇使用深度優(yōu)先搜索或廣度優(yōu)先搜索。

0 踩