aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--leetcode.c47
-rw-r--r--leetcode.h12
-rw-r--r--n_ary_tree_postorder_trav.c45
-rw-r--r--n_ary_tree_postorder_trav.py67
4 files changed, 171 insertions, 0 deletions
diff --git a/leetcode.c b/leetcode.c
index 66d2064..9ac1b03 100644
--- a/leetcode.c
+++ b/leetcode.c
@@ -16,6 +16,15 @@ void listnode_print(struct ListNode *head) {
printf("\n");
}
+void listnode_free(struct ListNode *head) {
+ struct ListNode *tmp;
+ while (head) {
+ tmp = head;
+ head = head->next;
+ free(tmp);
+ }
+}
+
struct TreeNode *treenode_create(int val) {
struct TreeNode *new = (struct TreeNode *)malloc(sizeof(struct TreeNode));
new->val = val;
@@ -31,3 +40,41 @@ void treenode_print(struct TreeNode *root) {
printf("%d ", root->val);
treenode_print(root->right);
}
+
+void treenode_free(struct TreeNode *root) {
+ if (!root)
+ return;
+ treenode_free(root->left);
+ treenode_free(root->right);
+ free(root);
+}
+
+struct Node *node_create(int val, int numChildren) {
+ struct Node *new = (struct Node *)malloc(sizeof(struct Node));
+ new->val = val;
+ new->numChildren = numChildren;
+ if (numChildren) {
+ new->children = (struct Node **)malloc(numChildren * sizeof(struct Node *));
+ for (int i = 0; i < numChildren; i++)
+ new->children[i] = NULL;
+ } else
+ new->children = NULL;
+ return new;
+}
+
+void node_print(struct Node *root, int depth) {
+ if (!root)
+ return;
+ printf("%d\n", root->val);
+ for (int i = 0; i < root->numChildren; i++)
+ node_print(root->children[i], depth + 1);
+}
+
+void node_free(struct Node *root) {
+ if (!root)
+ return;
+ for (int i = 0; i < root->numChildren; i++)
+ node_free(root->children[i]);
+ free(root->children);
+ free(root);
+}
diff --git a/leetcode.h b/leetcode.h
index c881193..6cdd131 100644
--- a/leetcode.h
+++ b/leetcode.h
@@ -57,11 +57,23 @@ struct TreeNode {
struct TreeNode *right;
};
+struct Node {
+ int val;
+ int numChildren;
+ struct Node **children;
+};
+
struct ListNode *listnode_create(int val);
void listnode_print(struct ListNode *head);
+void listnode_free(struct ListNode *head);
struct TreeNode *treenode_create(int val);
void treenode_print(struct TreeNode *root);
+void treenode_free(struct treeTreeNode *root);
+
+struct Node *node_create(int val, int numChildren);
+void node_print(struct Node *root, int depth);
+void node_free(struct Node *root);
#define IS_ARRAY(value) \
(!__builtin_types_compatible_p(typeof((value)), typeof(&(value)[0])))
diff --git a/n_ary_tree_postorder_trav.c b/n_ary_tree_postorder_trav.c
new file mode 100644
index 0000000..0dd9c89
--- /dev/null
+++ b/n_ary_tree_postorder_trav.c
@@ -0,0 +1,45 @@
+// 590. N-ary Tree Postorder Traversal
+#include "leetcode.h"
+
+/*
+ * 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 null value.
+ */
+
+void *post_vis(struct Node *root, int *n, int *idx) {
+ int i = 0, cnt[1000] = {0};
+ struct Node *prev[1000];
+ prev[i++] = NULL;
+ while (root) {
+ if (root->numChildren == cnt[i]) {
+ n[(*idx)++] = root->val;
+ cnt[i--] = 0;
+ root = prev[i];
+ } else {
+ prev[i] = root;
+ root = root->children[cnt[i++]++];
+ }
+ }
+ return NULL;
+}
+
+int *postorder(struct Node *root, int *returnSize) {
+ int *n = (int *)calloc(10000, sizeof(int)), idx = 0;
+ post_vis(root, n, &idx);
+ *returnSize = idx;
+ return n;
+}
+
+int main() {
+ struct Node *root = node_create(1, 3);
+ root->children[0] = node_create(3, 2);
+ root->children[1] = node_create(2, 0);
+ root->children[2] = node_create(4, 0);
+ root->children[0]->children[0] = node_create(5, 0);
+ root->children[0]->children[1] = node_create(6, 0);
+ int rs, *p = postorder(root, &rs);
+ for (int i = 0; i < rs; i++)
+ printf("%d ", p[i]); // expect: 5 6 3 2 4 1
+ free(p);
+}
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,
+ ]
+ )