aboutsummaryrefslogtreecommitdiff
path: root/n_ary_tree_postorder_trav.py
blob: 41f91dcf502da402b12608f325f221ede1b8f77d (plain)
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# 590. N-ary Tree Postorder Traversal

"""
given the 'root' of an n-ary tree, return the postorder traversal of its
nodes' values. nary-tree input serialisation is represented in their level
order traversal. each group of children is separated by the None value.
"""


# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children


class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        ans = []
        if not root:
            return ans

        def dfs(root, ans):
            for child in root.children:
                dfs(child, ans)
            ans.append(root.val)

        dfs(root, ans)
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.postorder(root=[1, None, 3, 2, 4, None, 5, 6]))
    print(
        root=[
            1,
            None,
            2,
            3,
            4,
            5,
            None,
            None,
            6,
            7,
            None,
            8,
            None,
            9,
            10,
            None,
            None,
            11,
            None,
            12,
            None,
            13,
            None,
            None,
            14,
        ]
    )