N叉树的前序遍历
N叉树的后序遍历
"""
# 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
