N-Array Tree to Binary Tree

https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree/

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

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

"""
# 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