N叉树的前、后序遍历 （Python）

N叉树的前、后序遍历 （Python）

​

递归 （由二叉树的递归演化，左右子节点变为子节点列表）

后序

"""# 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]: res_list = [] def dfs(root: 'Node'): if not root: return for cn in root.children: dfs(cn) res_list.append(root.val) dfs(root) return res_list

前序

"""# 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]: res_list = [] def dfs(root: 'Node'): if not root: return res_list.append(root.val) for cn in root.children: dfs(cn) dfs(root) return res_list

迭代 (其实就是二叉树前、后序遍历常规方法的扩展，左右子节点变成了子节点列表遍历，顺序仍然一致)

后序

"""# 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 [] res_list, stack = [], [(0, root)] while stack: flag, node = stack.pop() if flag == 1: res_list.append(node.val) else: stack.append((1, node)) for cn in node.children[::-1]: stack.append((0, cn)) return res_list

前序

"""# 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 [] res_list, stack = [], [root] while stack: tmp = stack.pop() res_list.append(tmp.val) stack.extend(tmp.children[::-1]) return res_list

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。