这篇文章主要介绍“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叉树的三种遍历怎么实现”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注编程网网站,小编会继续努力为大家带来更多实用的文章!