"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
# Definition for a Binary Tree Node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
"""
class Codec:
def encode(self, root):
if not root:
return None
b_root = TreeNode(root.val)
if root.children:
b_root.left = self._encode_children(root.children)
return b_root
def _encode_children(self, children):
head = None
cur = None
for child in children:
node = TreeNode(child.val)
node.left = self._encode_children(child.children)
if not head:
head = node
else:
cur.right = node
cur = node
return head
def decode(self, data):
if not data:
return None
n_root = Node(data.val, [])
n_root.children = self._decode_children(data.left)
return n_root
def _decode_children(self, node):
children = []
while node:
n_node = Node(node.val, self._decode_children(node.left))
children.append(n_node)
node = node.right
return children
/*
// 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.
class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
*/
class Codec {
public:
TreeNode* encode(Node* root) {
if (!root) return nullptr;
TreeNode* bRoot = new TreeNode(root->val);
if (!root->children.empty()) {
bRoot->left = encodeChildren(root->children);
}
return bRoot;
}
TreeNode* encodeChildren(const vector<Node*>& children) {
TreeNode* head = nullptr;
TreeNode* cur = nullptr;
for (Node* child : children) {
TreeNode* node = new TreeNode(child->val);
node->left = encodeChildren(child->children);
if (!head) head = node;
else cur->right = node;
cur = node;
}
return head;
}
Node* decode(TreeNode* data) {
if (!data) return nullptr;
Node* nRoot = new Node(data->val, {});
nRoot->children = decodeChildren(data->left);
return nRoot;
}
vector<Node*> decodeChildren(TreeNode* node) {
vector<Node*> children;
while (node) {
Node* nNode = new Node(node->val, decodeChildren(node->left));
children.push_back(nNode);
node = node->right;
}
return children;
}
};
/*
// 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.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
*/
class Codec {
public TreeNode encode(Node root) {
if (root == null) return null;
TreeNode bRoot = new TreeNode(root.val);
if (root.children != null && !root.children.isEmpty()) {
bRoot.left = encodeChildren(root.children);
}
return bRoot;
}
private TreeNode encodeChildren(List<Node> children) {
TreeNode head = null, cur = null;
for (Node child : children) {
TreeNode node = new TreeNode(child.val);
node.left = encodeChildren(child.children);
if (head == null) head = node;
else cur.right = node;
cur = node;
}
return head;
}
public Node decode(TreeNode data) {
if (data == null) return null;
Node nRoot = new Node(data.val, new ArrayList<>());
nRoot.children = decodeChildren(data.left);
return nRoot;
}
private List<Node> decodeChildren(TreeNode node) {
List<Node> children = new ArrayList<>();
while (node != null) {
Node nNode = new Node(node.val, decodeChildren(node.left));
children.add(nNode);
node = node.right;
}
return children;
}
}
/**
* // Definition for a Node.
* function Node(val, children) {
* this.val = val;
* this.children = children || [];
* };
*
* // Definition for a Binary Tree Node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var Codec = function() {};
Codec.prototype.encode = function(root) {
if (!root) return null;
let bRoot = new TreeNode(root.val);
if (root.children.length > 0) {
bRoot.left = this._encodeChildren(root.children);
}
return bRoot;
};
Codec.prototype._encodeChildren = function(children) {
let head = null, cur = null;
for (let child of children) {
let node = new TreeNode(child.val);
node.left = this._encodeChildren(child.children);
if (!head) head = node;
else cur.right = node;
cur = node;
}
return head;
};
Codec.prototype.decode = function(data) {
if (!data) return null;
let nRoot = new Node(data.val, []);
nRoot.children = this._decodeChildren(data.left);
return nRoot;
};
Codec.prototype._decodeChildren = function(node) {
let children = [];
while (node) {
let nNode = new Node(node.val, this._decodeChildren(node.left));
children.push(nNode);
node = node.right;
}
return children;
};
The "Encode N-ary Tree to Binary Tree" problem asks you to implement a pair of functions: one to encode an N-ary tree into a binary tree, and another to decode it back. An N-ary tree is a tree where each node can have any number of children, while a binary tree node can have at most two children (left and right).
You are provided with the root node of an N-ary tree and must write:
encode(root): Converts the N-ary tree to a binary tree.decode(data): Converts the binary tree back to the original N-ary tree.The main challenge is to represent the flexible structure of an N-ary tree using the limited structure of a binary tree. In an N-ary tree, each node can have an arbitrary number of children, but in a binary tree, each node can have only two children.
At first, one might consider storing all children in the left and right pointers directly, but this only supports two children per node. To handle more, we need a way to "chain" children together. A classic approach is the "left-child, right-sibling" representation:
left child in the binary tree.right pointer.left pointer for the first child and then following the right pointers for each sibling.
The key is to maintain this mapping during both encoding and decoding, ensuring the process is reversible.
We use the "left-child, right-sibling" technique to encode and decode the trees.
root is null, return null.left pointer.right child of the previous binary node.data is null, return null.left child; this gives the first N-ary child.right pointers to decode all siblings, adding each as a child to the N-ary node.This approach ensures that the structure is preserved and that the process is fully reversible.
Consider the following N-ary tree:
Encoding:
left child of node 1.right child of node 2.right child of node 3.left child of 3, 6 is the right child of 5.The resulting binary tree structure:
left pointer to 2, add as first child.right to 3, add as next child.left to 5, add as child; follow right to 6, add as next child.right to 4, add as next child of root.The reconstructed N-ary tree matches the original.
Brute-force approach: If you tried to store all children in a binary tree node, you'd lose children beyond two, making it impossible to reconstruct the original tree. This is not feasible.
Optimized approach (left-child, right-sibling):
The key insight is to use the left-child, right-sibling technique to represent an N-ary tree as a binary tree. By chaining children using the left and right pointers, we can encode and decode trees of arbitrary degree efficiently and losslessly. This approach is both elegant and practical, and it demonstrates how clever data structure representations can overcome apparent structural limitations.