LeetCode #590 N-ary Tree Postorder Traversal

Posted on | Post modified | In , , , , , , ,

Problem

Given an n-ary tree, return the postorder traversal of its nodes’ values.

Example

given a 3-ary tree:

img

Return its postorder traversal as: [5,6,3,2,4,1].

Solution1

Method: Recursive

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        res = []
        if root == None:
            return res

        def recursion(root, res):
            for child in root.children:
                recursion(child, res)
            res.append(root.val)

        recursion(root, res)
        return res

Solution2

Method: Iterative

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        stack = [(root, False)]
        ret = []

        while stack:
            node, visited = stack.pop()            
            if not visited and node:
                if node:
                    stack.append((node, True))
                    if node.children:
                        for idx, child in enumerate(node.children[::-1]):
                            stack.append((child, False))
            if visited:
                ret.append(node.val)
                
        return ret

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        res = []
        if root == None: return res

        stack = [root]
        while stack:
            curr = stack.pop()
            res.append(curr.val)
            stack.extend(curr.children)

        return res[::-1]