python N叉樹的三種遍歷怎么實(shí)現(xiàn)

這篇文章主要介紹“python N叉樹的三種遍歷怎么實(shí)現(xiàn)”，在日常操作中，相信很多人在python N叉樹的三種遍歷怎么實(shí)現(xiàn)問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”python N叉樹的三種遍歷怎么實(shí)現(xiàn)”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！

1、層次遍歷

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
 
class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:
            return []
 
        queue = collections.deque()
        queue.append(root)
        res = []
 
        while queue:
            size = len(queue)
            temp = []
            for _ in range(size):
                node = queue.popleft()
                temp.append(node.val)
                if node.children:
                    queue.extend(node.children)
            res.append(temp)
        
        return res

2、前序遍歷

前序遍歷就是從左至右，先根后孩子；遞歸比較簡(jiǎn)單，迭代法的話需要借助一個(gè)輔助棧，把每個(gè)節(jié)點(diǎn)的孩子都?jí)喝霔Ｖ校?/strong>

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
 
class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        
        #迭代法
        stack, output = [root, ], []            
        while stack:
            root = stack.pop()
            output.append(root.val)
            stack.extend(root.children[::-1])
                
        return output
 
        #遞歸法
        res = []
 
        def helper(root):
            if not root:
                return 
            res.append(root.val)
            for children in root.children:
                helper(children)
        
        helper(root)
 
        return res

3、后序遍歷

在后序遍歷中，我們會(huì)先遍歷一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)，再遍歷這個(gè)節(jié)點(diǎn)本身。例如當(dāng)前的節(jié)點(diǎn)為 u，它的子節(jié)點(diǎn)為 v1, v2, v3 時(shí)，那么后序遍歷的結(jié)果為 [children of v1], v1, [children of v2], v2, [children of v3], v3, u，其中 [children of vk] 表示以 vk 為根節(jié)點(diǎn)的子樹的后序遍歷結(jié)果（不包括 vk 本身）。我們將這個(gè)結(jié)果反轉(zhuǎn)，可以得到 u, v3, [children of v3]', v2, [children of v2]', v1, [children of v1]'，其中 [a]' 表示 [a] 的反轉(zhuǎn)。此時(shí)我們發(fā)現(xiàn)，結(jié)果和前序遍歷非常類似，只不過前序遍歷中對(duì)子節(jié)點(diǎn)的遍歷順序是 v1, v2, v3，而這里是 v3, v2, v1。

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
 
class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
 
        #后續(xù)遍歷是先遍歷一個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn),在去遍歷這個(gè)節(jié)點(diǎn)本身
        
        #遞歸
        result = []
        def postHelper(root):
            if not root:
                return None
            children = root.children
            for child in children:
                postHelper(child)
            result.append(root.val)
 
        postHelper(root)
        return result
 
 
 
        #迭代法：輔助棧
        res = []
        stack = [root,]
 
        while stack:
            
            node = stack.pop()
            if node is not None:
                res.append(node.val)
            for children in node.children:
                stack.append(children)
        
        return res[::-1]

總結(jié)：N叉樹和二叉樹的差別不是很多，唯一的差別就是孩子很多不需要去判斷左右孩子了。

到此，關(guān)于“python N叉樹的三種遍歷怎么實(shí)現(xiàn)”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！