设计一个算法，可以将 N 叉树编码为二叉树，并能将该二叉树解码为原 N 叉树。一个 N 叉树是指每个节点都有不超过 N 个孩子节点的有根树。类似地，一个二叉树是指每个节点都有不超过 2 个孩子节点的有根树。你的编码 / 解码的算法的实现没有限制，你只需要保证一个 N 叉树可以编码为二叉树且该二叉树可以解码回原始 N 叉树即可。
/*
// 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) {
}
// Decodes your binary tree to an n-ary tree.
Node* decode(TreeNode* root) {
}
};
// 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
* }
*/
type Codec struct {
}
func Constructor() *Codec {
return &Codec{}
}
func (this *Codec) encode(root *Node) *TreeNode {
if root == nil {
return nil
}
tree := &TreeNode{Val: root.Val}
if 0 < len(root.Children) {
tree.Left = this.encode(root.Children[0])
cur := tree.Left
for _, c := range root.Children[1:] {
cur.Right = this.encode(c)
cur = cur.Right
}
}
return tree
}
func (this *Codec) decode(root *TreeNode) *Node {
if root == nil {
return nil
}
node := &Node{Val: root.Val}
cur := root.Left
for cur != nil {
node.Children = append(node.Children, this.decode(cur))
cur = cur.Right
}
return node
}
/**
* Your Codec object will be instantiated and called as such:
* obj := Constructor();
* bst := obj.encode(root);
* ans := obj.decode(bst);
*/
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=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
"""
class Codec:
# Encodes an n-ary tree to a binary tree.
def encode(self, root: 'Node') -> TreeNode:
if not root: return
res = TreeNode(root.val)
if root.children:
res.left = self.encode(root.children[0])
cur = res.left
for node in root.children[1:]:
cur.right = self.encode(node)
cur = cur.right
return res
# Decodes your binary tree to an n-ary tree.
def decode(self, data: TreeNode) -> 'Node':
if not data: return
res = Node(data.val, [])
cur = data.left
while cur:
res.children.append(self.decode(cur))
cur = cur.right
return res
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(root))
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=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
"""
class Codec:
def encode(self, root):
"""Encodes an n-ary tree to a binary tree.
:type root: Node
:rtype: TreeNode
"""
if root is None: return None
res = TreeNode(root.val)
if(len(root.children) != 0):
res.left = self.encode(root.children[0])
cur = res.left
for i in range(1, len(root.children)):
cur.right = self.encode(root.children[i])
cur = cur.right
return res
def decode(self, root):
"""Decodes your binary tree to an n-ary tree.
:type root: TreeNode
:rtype: Node
"""
if not root: return None
res = Node(root.val, [])
cur = root.left
while(cur):
res.children.append(self.decode(cur))
cur = cur.right
return res
# 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;
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 == NULL) return NULL;
TreeNode* tn = new TreeNode(root->val);
if (root->children.size() == 0) return tn;
TreeNode* c = encode(root->children[0]);
tn->left = c;
for (int i = 1; i < root->children.size(); i++) {
c->right = encode(root->children[i]);
c = c->right;
}
return tn;
}
// Decodes your binary tree to an n-ary tree.
Node* decode(TreeNode* root) {
if (root == NULL) return NULL;
Node* n = new Node(root->val);
if (root->left == NULL) return n;
TreeNode* s = root->left;
while(s!=NULL) {
n->children.push_back(decode(s));
s = s->right;
}
return n;
}
};
// 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; }
* }
*/
class Codec {
// Encodes an n-ary tree to a binary tree.
public TreeNode encode(Node root) {
if (root == null) return null;
TreeNode newRoot = new TreeNode(root.val);
List<Node> children = root.children;
//第一个子节点存在
TreeNode cur = null;
if (!children.isEmpty()) {
newRoot.left = encode(children.get(0));
cur = newRoot.left;
}
//如果还存在第二个子节点，把子节点挂在第一个子节点的右子树
for (int i = 1; i < children.size(); i++) {
cur.right = encode(children.get(i));
cur = cur.right;
}
return newRoot;
}
// Decodes your binary tree to an n-ary tree.
public Node decode(TreeNode root) {
if (root == null) return null;
Node newNode = new Node(root.val, new ArrayList<>());
TreeNode cur = root.left;
while (cur != null) {
newNode.children.add(decode(cur));
cur = cur.right;
}
return newNode;
}
}
// 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;
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; }
* }
*/
class Codec {
// Encodes an n-ary tree to a binary tree.
public TreeNode encode(Node root) {
if (root == null) {
return null;
}
TreeNode treeNode = new TreeNode(root.val);
treeNode.left = encodeHelper(root.children);
return treeNode;
}
public TreeNode encodeHelper(List<Node> children) {
if (children == null || children.size() == 0) {
return null;
}
TreeNode treeNode = new TreeNode(-1);
TreeNode current = treeNode;
for (Node node : children) {
current.right = encode(node);
current = current.right;
}
return treeNode.right;
}
// Decodes your binary tree to an n-ary tree.
public Node decode(TreeNode root) {
if (root == null) {
return null;
}
Node node = new Node(root.val);
node.children = decodeHelper(root.left);
return node;
}
public List<Node> decodeHelper(TreeNode treeNode) {
List<Node> children = new ArrayList<>();
while (treeNode != null) {
children.add(decode(treeNode));
treeNode = treeNode.right;
}
return children;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(root));
