多叉树与二叉树互转 (C++)

左孩子右兄弟

// LeetCode 431
/*
// 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:
    void enc(Node* src, TreeNode* dest) 
    {
        auto src_chs=src->children;
        auto q=dest;
        if(src_chs.size())
        {
            auto p=src_chs[0];
            auto t=new TreeNode(p->val);
            q->left=t;
            enc(p,t);
            q=t;
        }
        for(int i=1;ival);
            q->right=t;
            enc(p,t);
            q=t;
        }
    }

    // Encodes an n-ary tree to a binary tree.
    TreeNode* encode(Node* root) {
        if(root==nullptr) return nullptr;
        auto ans=new TreeNode(root->val);
        enc(root, ans);
        return ans;
    }

    void dec(TreeNode* src, Node* dest)
    {
        auto p=src->left;
        while(p)
        {
            dest->children.push_back(new Node(p->val));
            dec(p, dest->children.back());
            p=p->right;
        }
    }
	
    // Decodes your binary tree to an n-ary tree.
    Node* decode(TreeNode* root) {
        if(root==nullptr) return nullptr;
        auto ans=new Node(root->val);
        dec(root, ans);
        return ans;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.decode(codec.encode(root));