# N-Array Tree to Binary Tree

这道题很难想如果是第一次做。解法是下图：

![](https://1824821017-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M3rU5fVRA3qiBmK8Dbx%2F-M3z-QJnHofcp6_2gcw6%2F-M3z-lJnSA4piv_-Jg5p%2FScreen%20Shot%202020-04-03%20at%2012.47.02%20AM.png?alt=media\&token=f553f221-2c0f-4214-8f01-13bd3d1e4487)

中心思想就是把n-array node里最左边的child变成binary node的左孩子，然后剩下所有node成为左孩子的右孩子。 这样一个n-array node的所有孩子都到它的left subtree里面了。以此类推，所有node的child用右孩子来作为它**同level孩子**    的连接。而左孩子用来存放它n-tray node里的所有孩子。

```python
"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

"""
# Definition for a binary tree node.
class TreeNode(object):
    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 == None:
            return None
        node = TreeNode(root.val)
        children = root.children
        if len(children) > 0:
            node.left = self.encode(children[0])
            curr = node.left
            for child in children[1:]:
                curr.right = self.encode(child)
                curr = curr.right
        return node
    
    def decode(self, data):
        """Decodes your binary tree to an n-ary tree.
        :type data: TreeNode
        :rtype: Node
        """
        if not data:
            return None
        node = Node(data.val,[])
        children = []
        if data.left:
            children.append(self.decode(data.left))
            curr = data.left
            while curr.right:
                children.append(self.decode(curr.right))
                curr = curr.right
            node.children = children
        return node
```