N-ary tree postorder traversal
July 20, 2022
treeProblem URL: N-ary tree postorder traversal
We will traverse the tree with recursive DFS, as it is postorder traversal, we first traverse all the children and then append the root to our result.
"""
# 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 = []
def traverse(root, res):
if not root:
return
for node in root.children:
traverse(node, res)
res.append(root.val)
traverse(root, res)
return res
Time Complexity: O(n)
Space Complexity: O(n)