[LeetCode] Encode N-ary Tree to Binary Tree 将N叉树编码为二叉树

时间:2021-10-12 02:09:20

Design an algorithm to encode an N-ary tree into a binary tree and decode the binary tree to get the original N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. Similarly, a binary tree is a rooted tree in which each node has no more than 2 children. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that an N-ary tree can be encoded to a binary tree and this binary tree can be decoded to the original N-nary tree structure.

For example, you may encode the following 3-ary tree to a binary tree in this way:

[LeetCode] Encode N-ary Tree to Binary Tree 将N叉树编码为二叉树

Note that the above is just an example which might or might not work. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note:

  1. N is in the range of [1, 1000]
  2. Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.

这道题让我们将一棵N叉树编码为二叉树,其实还需要将二叉树解码回N叉树。题目中说了具体的编解码的方法无所谓,那么就怎么简单怎么来呗。首先想一下这道题的难点是什么,N叉树的特点的每个结点最多有N个子结点,而二叉树的每个结点最多只能有两个子结点,那么多余的子结点怎么办,当然只能继续子结点下继续累加,就像泡泡龙游戏一样,一个挂一个的。如何累,得确定一套具体的规则,这样解码的时候,反向来一遍就可以了。对于当前结点 root 的N个子结点的处理办法是,将第一个结点挂到二叉树的左子结点上,然后将后面的结点依次挂到右子结点,和右子结点的右子结点上,这样做的好处是,同一层的子结点都挂在右子结点上,而这些子结点自己的子结点都会挂在左子结点上,听起来很晕是么,那就举例说明一下吧,就用题目中的例子中的树好了(注意题目中说只要能把N叉树编码成二叉树,然后再解码回原N叉树,并不 care 到底编码成啥样的二叉树)。

N-ary Tree:

   /  |  \

 / \

Binary Tree:

   /

 / \

 \   \
     

我们可以看出,N叉树根结点1的第一个子结点3被挂到了二叉树的左子结点上,同一层的结点2挂到了结点3的右子结点上,同一层的结点4被挂到了结点2的右子结点上。而结点3本身的子结点也按照这个规律,第一个子结点5挂到了结点3的左子结点上,而同一排的结点6挂到了结点5的右子结点上。

对于解码,也是同样的规律,先根据根结点值新建一个空的N叉树结点,由于我们的编码规律,根结点是一定没有右子结点的,所以取出左子结点 cur,并且开始循环,如果 cur 结点存在,那么我们对 cur 递归调用解码函数,将返回的结点加入当前N叉树结点的 children 数组中,然后 cur 再赋值为其右子结点,继续递归调用解码函数,再加入 children 数组,如此便可将二叉树还原为之前的N叉树,参见代码如下:

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

类似题目:

Serialize and Deserialize N-ary Tree

参考资料:

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

https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree/discuss/153061/Java-Solution-(Next-Level-greater-left-Same-Level-greater-right)

LeetCode All in One 题目讲解汇总(持续更新中...)

[LeetCode] Encode N-ary Tree to Binary Tree 将N叉树编码为二叉树的更多相关文章

  1. 【一天一道LeetCode】&num;104&period; Maximum Depth of Binary Tree

    一天一道LeetCode 本系列文章已全部上传至我的github,地址:ZeeCoder's Github 欢迎大家关注我的新浪微博,我的新浪微博 欢迎转载,转载请注明出处 (一)题目 来源:http ...

  2. 【LeetCode】297&period; Serialize and Deserialize Binary Tree 解题报告(Python)

    [LeetCode]297. Serialize and Deserialize Binary Tree 解题报告(Python) 标签: LeetCode 题目地址:https://leetcode ...

  3. 【LeetCode】662&period; Maximum Width of Binary Tree 解题报告(Python)

    [LeetCode]662. Maximum Width of Binary Tree 解题报告(Python) 标签(空格分隔): LeetCode 题目地址:https://leetcode.co ...

  4. 33&period; Minimum Depth of Binary Tree &amp&semi;&amp&semi; Balanced Binary Tree &amp&semi;&amp&semi; Maximum Depth of Binary Tree

    Minimum Depth of Binary Tree OJ: https://oj.leetcode.com/problems/minimum-depth-of-binary-tree/ Give ...

  5. &lbrack;LeetCode&rsqb; Verify Preorder Serialization of a Binary Tree 验证二叉树的先序序列化

    One way to serialize a binary tree is to use pre-oder traversal. When we encounter a non-null node, ...

  6. &lbrack;LeetCode&rsqb; Lowest Common Ancestor of a Binary Tree 二叉树的最小共同父节点

    Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According ...

  7. LeetCode之104&period; Maximum Depth of Binary Tree

    -------------------------------- 递归遍历即可 AC代码: /** * Definition for a binary tree node. * public clas ...

  8. 【LeetCode OJ】Maximum Depth of Binary Tree

    Problem Link: https://oj.leetcode.com/problems/maximum-depth-of-binary-tree/ Simply BFS from root an ...

  9. LeetCode Verify Preorder Serialization of a Binary Tree

    原题链接在这里:https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/ 题目: One way to ...

随机推荐

  1. 弹出iframe内嵌页面元素到父页面并全屏化

    (注册博客好久了,一直没舍得添砖加瓦,主要是每次想写点东西的时候,随便搜一搜发现都比我总结的都要好,甚感尴尬,但是总是要开始的,所以这就是我的第一篇博客,也绝不会是最后一篇,废话不多说,直接入正题) ...

  2. jQuery初学&colon;find&lpar;&rpar;方法及children方法的区别分析

    首先看看英文解释吧: children方法: find方法: 通过以上的解释,可以总结如下: 1:children及find方法都用是用来获得element的子elements的,两者都不会返回 te ...

  3. Verilog笔记——YUV2RGB的模块测试

    1 YUV2RGB的模块如下: module yuv2rgb( clk, //时钟输入 rstn, //复位输入,低电平复位 y_in, //变换前Y分量输出 cb_in, //变换前Cb分量输出 c ...

  4. VBA 小知识

    1. 循环 Dim i As Integer 'body Next 'body Wend 2. 键值数据结构 'create dictionary object Set dictMembers = C ...

  5. JS疑难点和GC原理

    js解析与序列化json数据(一)json.stringify()的基本用法: 对象有两个方法:stringify()和parse().在最简单的情况下,这两个方法分别用于把JavaScript对象序 ...

  6. bc&num;29 做题笔记

    昨天的bc被坑惨了= = 本来能涨rating的大好机会又浪费了...大号已弃号 A:第一反应是高精度,结果模板找不到了= =,然后现学现卖拍了个java的BigInteger+快速幂,调了好半天不说 ...

  7. SAX PULL解析实例

    XML三种解析方式: SAX解析:基于事件驱动,事件机制基于回调函数的,得到节点和节点之间内容时也会回调事件 PULL解析:相同基于事件驱动,仅仅只是回调时是常量 DOM解析:是先把XML文件装入内存 ...

  8. postman headers 请求参数和MD5加密签名

    postman 变量可以这样写:{{timestamp}} ,也可以用系统的,{{$timestamp}},这样就不用给自己赋值了,但在 pre-requestScript中是获取不到这个值的 所以我 ...

  9. Apache-Flink深度解析-SQL概览

    你可能感兴趣的文章: Flink入门 Flink DataSet&DataSteam API Flink集群部署 Flink重启策略 Flink分布式缓存 Flink重启策略 Flink中的T ...

  10. python的各种推导式

    python的各种推导式(列表推导式.字典推导式.集合推导式) 推导式comprehensions(又称解析式),是Python的一种独有特性.推导式是可以从一个数据序列构建另一个新的数据序列的结构体 ...