python N叉树的三种遍历怎么实现

这篇文章主要介绍“python N叉树的三种遍历怎么实现”，在日常操作中，相信很多人在Python N叉树的三种遍历怎么实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”python 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叉树和二叉树的差别不是很多，唯一的差别就是孩子很多不需要去判断左右孩子了。

到此，关于“python N叉树的三种遍历怎么实现”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注编程网网站，小编会继续努力为大家带来更多实用的文章！