LeetCode刷题实战431：将 N 叉树编码为二叉树-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 将 N 叉树编码为二叉树，我们先来看题面：

https://leetcode-cn.com/problems/encode-n-ary-tree-to-binary-tree/

设计一个算法，可以将 N 叉树编码为二叉树，并能将该二叉树解码为原 N 叉树。

一个 N 叉树是指每个节点都有不超过 N 个孩子节点的有根树。

类似地，一个二叉树是指每个节点都有不超过 2 个孩子节点的有根树。

你的编码 / 解码的算法的实现没有限制，你只需要保证一个 N 叉树可以编码为二叉树且该二叉树可以解码回原始 N 叉树即可。

解题

思路：参考官方思路，第一个子节点2接到父节点1的left，其余的兄弟节点 3，4 都接在其左边兄弟节点的right

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector _children) {
        val = _val;
        children = _children;
    }
};
*/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

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