Encode N Ary Tree To Binary Tree - Leetcode Solution

Problem Description:

Given an n-ary tree, encode it into a binary tree and decode it back to the original n-ary tree. The encoding of an n-ary tree into a binary tree is done as follows:

• The root of the n-ary tree becomes the root of the binary tree.
• For each child of the n-ary tree root, create a new binary tree node and make it the left child of the corresponding binary tree node.
• For each sibling of the n-ary tree root, create a new binary tree node and make it the right child of the corresponding binary tree node.

Solution:

We can solve this problem using a recursive approach. Let's start by defining the Data Structures.

1. Definition of n-ary tree

class Node { public: int val; vector<Node*> children; Node(int val) : val(val) {}; };

2. Definition of binary tree

class TreeNode { public: int val; TreeNode* left; TreeNode* right; TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}; };

We will start with the encode function, which takes an n-ary tree root node as input and returns its corresponding binary tree root.

TreeNode* encode(Node* root) { if (root == nullptr) return nullptr;

TreeNode* binaryRoot = new TreeNode(root->val);

// If n-ary tree has no children, then return the binary tree root.
if (root->children.empty()) return binaryRoot;

// Set the left child of binary tree node to the first child of the n-ary tree node.
binaryRoot->left = encode(root->children[0]);
TreeNode* cur = binaryRoot->left;

// For every other child of n-ary tree node, create a new binary tree node and assign it to the right child of the previous node.
for (int i = 1; i < root->children.size(); ++i) {
    cur->right = encode(root->children[i]);
    cur = cur->right;
}

return binaryRoot;

}

Let's understand the solution of each step of encoding process.

In step 1, if n-ary tree root is null, then return null.

In step 2, if the n-ary tree has only one child, then create a new binary tree node and assign the left child of the binary tree to it. Otherwise, create a new binary tree node and assign its left child as the first child of the n-ary tree node.

In step 3, create a new binary tree node for every other child of n-ary tree node and assign its right child to the previous binary tree node's right child.

Now let's move on to the decode function, which takes binary tree root as input and returns its corresponding n-ary tree root node.

Node* decode(TreeNode* root) { if (root == nullptr) return nullptr;

Node* nAryRoot = new Node(root->val);
TreeNode* cur = root->left;

while (cur != nullptr) {
    nAryRoot->children.push_back(decode(cur));
    cur = cur->right;
}

return nAryRoot;

}

In the decode function, we have used a while loop, which iterates through the right children of the binary tree nodes and recursively builds n-ary tree.

In conclusion, the problem "Encode N Ary Tree To Binary Tree" on LeetCode can be solved by converting the given n-ary tree into a binary tree first and then converting it back to the n-ary tree using recursive methods.

1