文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 遞歸
    • 2.2 BFS

1. 題目

設(shè)計(jì)一個(gè)算法，可以將 N 叉樹編碼為二叉樹，并能將該二叉樹解碼為原 N 叉樹。
一個(gè) N 叉樹是指每個(gè)節(jié)點(diǎn)都有不超過 N 個(gè)孩子節(jié)點(diǎn)的有根樹。
類似地，一個(gè)二叉樹是指每個(gè)節(jié)點(diǎn)都有不超過 2 個(gè)孩子節(jié)點(diǎn)的有根樹。
你的編碼 / 解碼的算法的實(shí)現(xiàn)沒有限制，你只需要保證一個(gè) N 叉樹可以編碼為二叉樹且該二叉樹可以解碼回原始 N 叉樹即可。

例如，你可以將下面的 3-叉 樹以該種方式編碼：

注意，上面的方法僅僅是一個(gè)例子，可能可行也可能不可行。
你沒有必要遵循這種形式轉(zhuǎn)化，你可以自己創(chuàng)造和實(shí)現(xiàn)不同的方法。

注意：
N 的范圍在 [1, 1000]
不要使用類成員 / 全局變量 / 靜態(tài)變量來存儲(chǔ)狀態(tài)。
你的編碼和解碼算法應(yīng)是無狀態(tài)的。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/encode-n-ary-tree-to-binary-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 參考官方思路，第一個(gè)子節(jié)點(diǎn)2接到父節(jié)點(diǎn)1的left，其余的兄弟節(jié)點(diǎn) 3，4 都接在其左邊兄弟節(jié)點(diǎn)的right
  

2.1 遞歸

/* // Definition for a Node. class Node { public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _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;} };

108 ms 179.4 MB

2.2 BFS

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), *newTreeNode = NULL;TreeNode* cur = NULL;queue<pair<Node*, TreeNode*>> q;q.push({root,newroot});while(!q.empty()){int size = q.size();while(size--){root = q.front().first;newTreeNode = q.front().second;q.pop();if(!root->children.empty()){newTreeNode->left = new TreeNode(root->children[0]->val);cur = newTreeNode->left;q.push({root->children[0], cur});}for(int i = 1; i < root->children.size(); ++i){cur->right = new TreeNode(root->children[i]->val);;cur = cur->right;q.push({root->children[i], cur});}}}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), *newNode = NULL;Node *cur = NULL;queue<pair<TreeNode*, Node*>> q;q.push({root,newroot});while(!q.empty()){int size = q.size();while(size--){root = q.front().first;cur = q.front().second;q.pop();if(root->left){newNode = new Node(root->left->val);cur->children.push_back(newNode);q.push({root->left, newNode});root = root->left;while(root->right){newNode = new Node(root->right->val);cur->children.push_back(newNode);q.push({root->right, newNode});root = root->right;}}}}return newroot;} };

80 ms 173.6 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 431. 将 N 叉树编码为二叉树（递归/层序）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。