The first child of a node becomes the left child in the binary tree.
Subsequent children become the right child of the previous child, forming a sibling chain.

Decoding:

Reverse the transformation by reconstructing the N-ary tree from the binary tree.

This encoding effectively maintains the N-ary relationships while conforming to the binary tree structure.

Code

[{"language":"Java","code":"class Node {\n    public int val;\n    public List<Node> children;\n\n    public Node() {}\n\n    public Node(int _val, List<Node> _children) {\n        val = _val;\n        children = _children;\n    }\n}\n\nclass TreeNode {\n    int val;\n    TreeNode left;\n    TreeNode right;\n\n    TreeNode(int x) {\n        val = x;\n    }\n}\n\nclass Codec {\n    // Method to encode N-ary tree (Node) to Binary tree (TreeNode)\n    public TreeNode encode(Node root) {\n        if (root == null) return null;\n        TreeNode ans = new TreeNode(root.val);\n        if (root.children == null || root.children.isEmpty()) return ans;\n\n        // First child becomes the left child\n        ans.left = encode(root.children.get(0));\n        TreeNode curr = ans.left;\n\n        // Subsequent children are linked as right siblings\n        for (int i = 1; i < root.children.size(); i++) {\n            curr.right = encode(root.children.get(i));\n            curr = curr.right;\n        }\n        return ans;\n    }\n\n    // Method to decode Binary tree (TreeNode) back to N-ary tree (Node)\n    public Node decode(TreeNode root) {\n        if (root == null) return null;\n        Node ans = new Node(root.val, new ArrayList<>());\n        TreeNode curr = root.left;\n\n        // Expand the left child chain into the children list\n        while (curr != null) {\n            ans.children.add(decode(curr));\n            curr = curr.right;\n        }\n        return ans;\n    }\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Node</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> val;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    public</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> List&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">Node</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">> children;</span></span>\n<span class=\"line\"></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    public</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Node</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">() {}</span></span>\n<span class=\"line\"></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    public</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Node</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> _val</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, List&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">Node</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">> </span><span style=\"color:#E362

Related Tags