# N-ary Tree

###### tags: `LeetCode筆記`

## :memo: 一、Definition

If a tree is a rooted tree in which each node has no more than **N** children, it is called **N-ary tree**.


## :memo: 二、Traversal

### 1. Preorder Traversal
A->B->C->E->F->D->G
#### C

void traverse(int* ret, int* index, struct Node* root)
{
    if (root == NULL)
    {
        return NULL;
    }
    
    ret[*index] = root->val;
    (*index)++;
    
    for (int i = 0; i < root->numChildren; i++)
    { 
        if (root->children[i] != NULL)
        {
            traverse(ret, index, root->children[i]);
        }
    }
    
}

int* preorder(struct Node* root, int* returnSize)
{
    int* ret = (int*) malloc(sizeof(int) * 10000);
    int index = 0;
    
    traverse(ret, &index, root);
    *returnSize = index;
    
    return ret;
}

#### C++

class Solution {
public:
    void preorder_traverse(Node* root, vector<int>& res) {
        if (root == nullptr) {
            return;
        }
        
        res.push_back(root->val);
        
        for (int i = 0; i < (root->children).size(); i++) {
            preorder_traverse(root->children[i], res);
        }
    }
    
    vector<int> preorder(Node* root) {
        vector<int> res;
        
        preorder_traverse(root, res);
        
        return res;
    }
};

#### C++ with stack

class Solution {
public:
    vector<int> preorder(Node* root) {
        if (!root) {
            return {};
        }
        Node* temp = root;
        stack<Node*> s;
        vector<int> res;
        s.push(temp);
        while (!s.empty()) {
            temp = s.top();
            if (!temp->children.empty()) {
                res.push_back(s.top()->val);
                s.pop();
                for (int i = temp->children.size() - 1; i >= 0; i--){
                    s.push(temp->children[i]);
                }
            }
            else {
                res.push_back(s.top()->val);
                s.pop();
            }
        }

        return res;
    }
};

### 2. Postorder Traversal
B->E->F->C->G->D->A
#### C

void traverse(int* ret, int* index, struct Node* root)
{
    if (root == NULL)
    {
        return;
    }
    
    for (int i = 0; i < root->numChildren; i++)
    {
        if (root->children[i] != NULL)
        {
            traverse(ret, index, root->children[i]);
        }
    }
    
    ret[*index] = root->val;
    (*index)++;
    
}
int* postorder(struct Node* root, int* returnSize)
{
    int* ret =(int*) malloc(sizeof(int) * 10000);
    int index = 0;
    
    traverse(ret, &index, root);
    *returnSize = index;
    
    return ret;
}

#### C++

class Solution {
public:
    void postorder_trverse(Node* root, vector<int>& res) {
        if (root == nullptr) {
            return;
        }
        
        for (int i = 0; i < (root->children).size(); i++) {
            postorder_trverse(root->children[i], res);
        }
        
        res.push_back(root->val);
    }
    
    vector<int> postorder(Node* root) {
        vector<int> res;
        
        postorder_trverse(root, res);
        
        return res;
    }
};

### 3. Level-order Traversal
A->B->C->D->E->F->G
#### C with recursion

int maxHeight(struct Node* root)
{
    if (root == NULL)
    {
        return 0;
    }
    if (root->numChildren == 0)
    {
        return 1;
    }
    int max = 0;
    for (int i = 0; i < root->numChildren; i++)
    {
        int tmp = maxHeight(root->children[i]) + 1;
        max = tmp > max? tmp : max;
    }
    
    return max;
}

void traverse(struct Node* root, int** ret, int ridx, int** returnColumnSizes)
{
    if (root == NULL)
    {
        return;
    }
    ret[ridx][(*returnColumnSizes)[ridx]] = root->val;
    (*returnColumnSizes)[ridx]++;
    for (int i = 0; i < root->numChildren; i++)
    {
        traverse(root->children[i], ret, ridx + 1, returnColumnSizes);
    }
}

int** levelOrder(struct Node* root, int* returnSize, int** returnColumnSizes)
{
    int Height = maxHeight(root);
    *returnSize = Height;
    *returnColumnSizes = (int*)calloc(Height,sizeof(int));
    int** ret = (int**)malloc(Height*sizeof(int*));
    for(int i=0;i<Height;i++)
    {
        ret[i] = (int*)malloc(sizeof(int)*10000);
    }
    traverse(root,ret,0,returnColumnSizes);
    
    return ret;
}

#### C++ BFS using a Queue

class Solution {
public:    
    vector<vector<int>> levelOrder(Node* root) {
        if (root == nullptr) {
            return {};
        }
        vector<vector<int>> res;
        queue<Node*> q;        
        vector<int> temp;
        
        temp.push_back(root->val);
        res.push_back(temp);
        
        q.push(root);        
        while (!q.empty()) {
            int Q_size = q.size();
            vector<int> temp;
            for (int i = 0; i < Q_size; i++) {
                Node* curr = q.front();
                q.pop();
                for (int j = 0; j < curr->children.size(); j++) {
                    if (curr->children[j] != nullptr) {
                        temp.push_back(curr->children[j]->val);
                        q.push(curr->children[j]);
                    }
                }
            }
            res.push_back(temp);
        }
        
        res.pop_back();
        return res;
    }
};

### Note:
there is no standard definition for in-order traversal in n-ary trees.

## :memo: Maximum Depth of N-ary Tree (Easy)


### 作法
檢查children的size，0就回傳1，非0就繼續遞迴

class Solution {
public:
    int maxDepth(Node* root) {
        if (root == nullptr) {
            return 0;
        }
        
        if (root->children.size() == 0) {
            return 1;
        }
        
        int res = INT_MIN;
        for (int i = 0; i < root->children.size(); i++) {   
            res = max(maxDepth(root->children[i]) + 1, res);
        }
        
        return res;
    }
};

## :memo: Encode N-ary Tree to Binary Tree (Hard)

### 作法 C++

class Codec {
public:
    
    // Encodes an n-ary tree to a binary tree.
    TreeNode* encode(Node* root) {
        //left child: child chain, right child: lower siblings
        if (root == NULL) return NULL;
        TreeNode* ret = new TreeNode(root->val);
        if (root->children.size() == 0) return ret;
        ret->left = encode(root->children[0]);
        TreeNode* now = ret->left;
        for (int i = 1; i < root->children.size(); i++) {
            now->right = encode(root->children[i]);
            now = now->right;
        }
        return ret;
    }
    
    // Decodes your binary tree to an n-ary tree.
    Node* decode(TreeNode* root) {
        if (root == NULL) return NULL;
        Node* ret = new Node;
        ret->val = root->val;
        TreeNode* now = root->left;
        while(now) {
            ret->children.push_back(decode(now));
            now = now->right;
        }
        return ret;
    }
    
};

## :memo: Serialize and Deserialize N-ary Tree (Hard)
https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree/description/

### 作法 C++

class Codec {
public:
    //rule: root, number of child, each child
    
    // Encodes a tree to a single string.
    string serialize(Node* root) {
        string s;
        encode_dfs(root, s);
        return s;
    }
    
    void encode_dfs(Node* root, string& s) {
        if(!root) return;
        s += " " + to_string(root->val) + " " + to_string(root->children.size());
        for (auto p: root->children) encode_dfs(p, s);
    }
	
    // Decodes your encoded data to tree.
    Node* deserialize(string data) {
        stringstream ss(data);
        return decode(ss);
    }
    
    Node* decode(stringstream& ss) {
        ss.peek();
        if (ss.eof()) return nullptr;
        auto root = new Node();
        int child_size;
        ss >> root->val >> child_size;
        for (int i = 0; i < child_size; i++) root->children.push_back(decode(ss));
        return root;
    }
};

## :memo: 刷題檢討
學會**基本traversal**和**算高度**，難題用C++去解:
1. 多子樹與二元樹轉換
2. 解析多子樹