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.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See following example).
For example, you may encode the following 3-ary tree to a binary tree in this way:
Input: root = [1,null,3,2,4,null,5,6]
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.
The number of nodes in the tree is in the range [0, 104].
0 <= Node.val <= 104
The height of the n-ary tree is less than or equal to 1000
Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
Solutions
Solution 1: Recursion
We can point the left pointer of the binary tree to the first child of the N-ary tree and the right pointer of the binary tree to the next sibling node of the N-ary tree.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the N-ary tree.
"""# Definition for a Node.class Node: def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None): self.val = val self.children = children""""""# Definition for a binary tree node.class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None"""classCodec:# Encodes an n-ary tree to a binary tree.defencode(self,root:"Optional[Node]")->Optional[TreeNode]:ifrootisNone:returnNonenode=TreeNode(root.val)ifnotroot.children:returnnodeleft=self.encode(root.children[0])node.left=leftforchildinroot.children[1:]:left.right=self.encode(child)left=left.rightreturnnode# Decodes your binary tree to an n-ary tree.defdecode(self,data:Optional[TreeNode])->"Optional[Node]":ifdataisNone:returnNonenode=Node(data.val,[])ifdata.leftisNone:returnnodeleft=data.leftwhileleft:node.children.append(self.decode(left))left=left.rightreturnnode# Your Codec object will be instantiated and called as such:# codec = Codec()# codec.decode(codec.encode(root))
/*// Definition for a Node.class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; }};*//** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */classCodec{// Encodes an n-ary tree to a binary tree.publicTreeNodeencode(Noderoot){if(root==null){returnnull;}TreeNodenode=newTreeNode(root.val);if(root.children==null||root.children.isEmpty()){returnnode;}TreeNodeleft=encode(root.children.get(0));node.left=left;for(inti=1;i<root.children.size();i++){left.right=encode(root.children.get(i));left=left.right;}returnnode;}// Decodes your binary tree to an n-ary tree.publicNodedecode(TreeNodedata){if(data==null){returnnull;}Nodenode=newNode(data.val,newArrayList<>());if(data.left==null){returnnode;}TreeNodeleft=data.left;while(left!=null){node.children.add(decode(left));left=left.right;}returnnode;}}// Your Codec object will be instantiated and called as such:// Codec codec = new Codec();// codec.decode(codec.encode(root));
/*// 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) {} * }; */classCodec{public:// Encodes an n-ary tree to a binary tree.TreeNode*encode(Node*root){if(root==nullptr){returnnullptr;}TreeNode*node=newTreeNode(root->val);if(root->children.empty()){returnnode;}TreeNode*left=encode(root->children[0]);node->left=left;for(inti=1;i<root->children.size();i++){left->right=encode(root->children[i]);left=left->right;}returnnode;}// Decodes your binary tree to an n-ary tree.Node*decode(TreeNode*data){if(data==nullptr){returnnullptr;}Node*node=newNode(data->val,vector<Node*>());if(data->left==nullptr){returnnode;}TreeNode*left=data->left;while(left!=nullptr){node->children.push_back(decode(left));left=left->right;}returnnode;}};// Your Codec object will be instantiated and called as such:// Codec codec;// codec.decode(codec.encode(root));
/** * Definition for a Node. * type Node struct { * Val int * Children []*Node * } *//** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */typeCodecstruct{}funcConstructor()*Codec{return&Codec{}}// Encodes an n-ary tree to a binary tree.func(this*Codec)encode(root*Node)*TreeNode{ifroot==nil{returnnil}node:=&TreeNode{Val:root.Val}iflen(root.Children)==0{returnnode}left:=this.encode(root.Children[0])node.Left=leftfori:=1;i<len(root.Children);i++{left.Right=this.encode(root.Children[i])left=left.Right}returnnode}// Decodes your binary tree to an n-ary tree.func(this*Codec)decode(data*TreeNode)*Node{ifdata==nil{returnnil}node:=&Node{Val:data.Val,Children:[]*Node{}}ifdata.Left==nil{returnnode}left:=data.Leftforleft!=nil{node.Children=append(node.Children,this.decode(left))left=left.Right}returnnode}/** * Your Codec object will be instantiated and called as such: * obj := Constructor(); * bst := obj.encode(root); * ans := obj.decode(bst); */