n 元树的节点结构如下：

struct NaryNode  
{  
    int data;  
    list<NaryNode*> children;  
    NaryNode(int _data):data(_data){}  
};  

能否将 n 元树转换为我们熟悉的二叉树？需要知道，这种转换一定是一一对应的，n 元树唯一映射成一棵二叉树，该二叉树也唯一映射成一棵 n 元树。答案是可以，只需将 children 放在该父节点的左树右边界上 ，如下图：

简单而言——左子树为子，右子树为兄，这样就能够保证映射的唯一性。下面提供广度优先和深度优先两种转换思路。

广度优先

广度优先的主要思路是：在 n 元树层序遍历的基础上添加了一些二叉树节点的创建和边界处理操作。

  TreeNode* convert(NaryNode* root)  
{  
    if(root == nullptr)  
        return nullptr;  
    TreeNode* biRoot = new TreeNode(root->data);  
    pair<NaryNode*, TreeNode*> tmp_pr;  
    queue<pair<NaryNode*, TreeNode*>> que;  
    que.push(pair(root, biRoot));  
    while(!que.empty())  
    {  
        tmp_pr = que.front();  
        que.pop();  
        if(!tmp_pr.first->children.empty()) 
        {  
            auto p = tmp_pr.first->children.begin();  
            while(p != tmp_pr.first->children.end()) //处理children
            {  
                if(p == tmp_pr.first->children.begin())//如果为长兄，则放在父节点的左孩子
                {  
                    TreeNode* nd = new TreeNode((*p)->data);  
                    tmp_pr.second->left = nd; //父节点的left指向长兄
                    que.push(pair(*p, nd));  
                    p++;  
                }  
                else //如果不为长兄，则放在长兄的右孩子
                {  
                    auto tmp = que.back(); //此处是取得上一次入栈的兄弟，使该兄弟的右孩子指向本节点
                    TreeNode* nd = new TreeNode((*p)->data);  
                    tmp.second->right = nd;  
                    que.push(pair(*p, nd));  
                    p++;  
                }  
            }  
        }  
    }  
    return biRoot;  
}  

这里有个问题是，为什么必须要用 pair 将原有的 NaryNode 和新创建的 TreeNode 绑定在一起？举例来说，如果你只创建 TreeNode 而不记录，那么在创建上图中的 e 节点时，你就无法将 b 节点的 left 指针指向 e ，因为之前创建 b 节点时你压根就没有记录它，该节点已经被丢失而无法利用了。

深度优先

TreeNode* convert_in(list<NaryNode*> children)
{
    if(children.empty())
        return nullptr;
    auto p = children.begin();
    TreeNode* head = new TreeNode((*p)->data);//长兄
    head->left = convert_in((*p)->children);
    p++;
    TreeNode* tmp = head;
    while(p != children.end())
    {
        tmp->right = new TreeNode((*p)->data);
        tmp = tmp->right;
        tmp->left = convert_in((*p)->children);
        p++;
    }
    return head;
}
TreeNode* convert(NaryNode* root)
{
    if(root == nullptr)
        return nullptr;
    TreeNode* binaryRoot = new TreeNode(root->data);
    binaryRoot->left = convert_in(root->children);
    return binaryRoot;
}

思路过程：

任务？

=> 将 children 挂在父节点的左树右边界上。

=> 所以可以写为：

binaryRoot->left = convert(NaryRoot->children)

那么 convert 内部怎么转换？

=> 易知 convert 最后一定会返回 children 中的长兄，不妨先创建该节点（第 7 行）。

=> 接着依次处理其他兄弟，并将它们连接起来（10-16）。

=> 每个兄弟又可能都会有自己的 children ，所以必须让兄弟们的 left 指针指向各自的 children ，于是添加第 7 行和第 14 行代码，完成。

int main()
{
//       1
//     / | \
//    2  3  4
//   /\\    /\\
//  8 9 10 5 6 7
    NaryNode* root = new NaryNode(1);
    root->children.push_back(new NaryNode(2));
    root->children.push_back(new NaryNode(3));
    root->children.push_back(new NaryNode(4));
    root->children.back()->children.push_back(new NaryNode(5));
    root->children.back()->children.push_back(new NaryNode(6));
    root->children.back()->children.push_back(new NaryNode(7));
    root->children.front()->children.push_back(new NaryNode(8));
    root->children.front()->children.push_back(new NaryNode(9));
    root->children.front()->children.push_back(new NaryNode(10));
    TreeNode* binaryRoot = convert(root);
}

最后得到的二叉树为：