diff options
-rw-r--r-- | leetcode.c | 47 | ||||
-rw-r--r-- | leetcode.h | 12 | ||||
-rw-r--r-- | n_ary_tree_postorder_trav.c | 45 | ||||
-rw-r--r-- | n_ary_tree_postorder_trav.py | 67 |
4 files changed, 171 insertions, 0 deletions
@@ -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); +} @@ -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, + ] + ) |