# 590. N-ary Tree Postorder Traversal

題目：<https://leetcode.com/problems/n-ary-tree-postorder-traversal/>

解法：DFS

Python3：

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

def listToTree(arr):
    nodes = [Node(arr[0], [])]
    i = 0
    j = 2
    length = len(arr)
    while j < length:
        if arr[j] is not None:
            tmp = Node(arr[j], [])
            nodes[i].children.append(tmp)
            nodes.append(tmp)
        else:
            i += 1
        j += 1
    return nodes[0]

def treeToList(root):
    from collections import deque
    nodes = deque()
    nodes.append(root)
    arr = []
    arr.append(root.val)
    arr.append(None)
    while len(nodes):
        node = nodes.popleft()
        for child in node.children:
            nodes.append(child)
            arr.append(child.val)
        arr.append(None)
    return arr

class Solution:
    def preorder(self, root: 'Node') -> list[int]:
        def dfs(node):
            if node:
                for child in node.children:
                    dfs(child)
                output.append(node.val)
        output = []
        dfs(root)        
        return output

if __name__ == '__main__':
    arr = [1, None, 3, 2, 4, None, 5, 6]
    root = listToTree(arr)
    print(treeToList(root))

    ans = Solution().preorder(root)
    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node {
    int val;
    int numChildren;
    struct Node** children;
};

struct Node* strToTree(char *str) {
    char *token = strtok(str, ",");
    struct Node **nodes = (struct Node**)malloc(sizeof(struct Node*));
    nodes[0] = (struct Node*)malloc(sizeof(struct Node));
    nodes[0]->val = atoi(token);
    nodes[0]->numChildren = 0;
    nodes[0]->children = NULL;
    int i = 0, len = 1;
    token = strtok(NULL, ",");
    token = strtok(NULL, ",");
    while (token != NULL) {
        if (strcmp(token, "null") != 0) {
            len++;
            nodes = (struct Node**)realloc(nodes, sizeof(struct Node*) * len);
            nodes[len - 1] = (struct Node*)malloc(sizeof(struct Node));
            nodes[len - 1]->val = atoi(token);
            nodes[len - 1]->numChildren = 0;
            nodes[len - 1]->children = NULL;
            nodes[i]->numChildren++;
            nodes[i]->children = (struct Node**)realloc(nodes[i]->children, sizeof(struct Node*) * (nodes[i]->numChildren));
            nodes[i]->children[(nodes[i]->numChildren) - 1] = nodes[len - 1];
        } else {
            i++;
        }
        token = strtok(NULL, ",");
    }
    return nodes[0];
}

void printLevelOrderWithNull(struct Node* root) {
    struct Node * bfs[10000] = {};
    bfs[0] = root;
    int i = 0, len = 1;
    printf("%d null ", root->val);
    while (i < len) {
        for (int j = 0; j < bfs[i]->numChildren; j++) {
            bfs[len++] = bfs[i]->children[j];
            printf("%d ", bfs[i]->children[j]->val);
        }
        printf("null ");
        i++;
    }
    printf("\n");
}

int* preorder(struct Node* root, int* returnSize) {
    int* output = (int*)malloc(sizeof(int) * 10000);
    
    void dfs(struct Node* cur) {
        if (cur == NULL)
            return;
        for (int i = 0; i < cur->numChildren; i++)
            dfs(cur->children[i]);
        output[(*returnSize)++] = cur->val;
    }
    
    *returnSize = 0;
    dfs(root);
    return output;
}

int main()
{
    char input[] = "1,null,3,2,4,null,5,6";
    struct Node* root = strToTree(input);
    printLevelOrderWithNull(root);
    printf("\n");
    
    int returnSize;
    int* ans = preorder(root, &returnSize);
    printf("%d\n", returnSize);
    for (int i = 0; i < returnSize; i++)
        printf("%d ", ans[i]);
    printf("\n");
    return 0;
}

###### tags: `leetcode` `tree` `depth-first search`