N叉树的三种遍历(层次遍历、前序遍历、后序遍历)

2024-04-02 19:04:59 411人浏览安东尼

摘要

目录题目链接：1、层次遍历2、前序遍历3、后序遍历题目链接： 590.N叉树的后序遍历 429.N叉树的层序遍历 598.N叉树的前序遍历 1、层次遍历 """ # Definit

题目链接：

590.N叉树的后序遍历

429.N叉树的层序遍历

598.N叉树的前序遍历

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、前序遍历

前序遍历就是从左至右，先根后孩子；递归比较简单，迭代法的话需要借助一个辅助栈，把每个节点的孩子都压入栈中；

"""
# 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、后序遍历

在后序遍历中，我们会先遍历一个节点的所有子节点，再遍历这个节点本身。例如当前的节点为 u，它的子节点为 v1, v2, v3 时，那么后序遍历的结果为 [children of v1], v1, [children of v2], v2, [children of v3], v3, u，其中 [children of vk] 表示以 vk 为根节点的子树的后序遍历结果（不包括 vk 本身）。我们将这个结果反转，可以得到 u, v3, [children of v3]', v2, [children of v2]', v1, [children of v1]'，其中 [a]' 表示 [a] 的反转。此时我们发现，结果和前序遍历非常类似，只不过前序遍历中对子节点的遍历顺序是 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 []
 
        #后续遍历是先遍历一个节点的孩子节点,在去遍历这个节点本身
        
        #递归
        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]

总结：N叉树和二叉树的差别不是很多，唯一的差别就是孩子很多不需要去判断左右孩子了。

到此这篇关于N叉树的三种遍历(层次遍历、前序遍历、后序遍历)的文章就介绍到这了,更多相关N叉树的三种遍历内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: N叉树的三种遍历(层次遍历、前序遍历、后序遍历)

本文链接: https://www.lsjlt.com/news/146053.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341