aboutsummaryrefslogtreecommitdiff
path: root/n_ary_tree_postorder_trav.py
diff options
context:
space:
mode:
Diffstat (limited to 'n_ary_tree_postorder_trav.py')
-rw-r--r--n_ary_tree_postorder_trav.py67
1 files changed, 67 insertions, 0 deletions
diff --git a/n_ary_tree_postorder_trav.py b/n_ary_tree_postorder_trav.py
new file mode 100644
index 0000000..41f91dc
--- /dev/null
+++ b/n_ary_tree_postorder_trav.py
@@ -0,0 +1,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,
+ ]
+ )