将 N 叉树编码为二叉树

这个题解通过将N叉树(N-ary Tree)编码为二叉树(Binary Tree)的方式解决了如何在二叉树的数据结构中表示一个N叉树的问题。编码过程中，每个N叉树节点的所有子节点被转换为二叉树中的左子树，其中每个子节点成为前一个子节点的右子节点。解码过程则是编码的逆过程，它通过遍历二叉树，重新构建出原始的N叉树结构。

时间复杂度: O(n)

空间复杂度: O(n)

"""
# 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, x):
        self.val = x
        self.left = None
        self.right = None
"""

class Codec:
    # Encodes an n-ary tree to a binary tree.
    def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:
        if root is None:
            return None
        
        binary_root = TreeNode(root.val) # 创建二叉树的根节点
        if root.children:
            binary_root.left = self.encode_children(root.children) # 将N叉树的所有子节点编码为二叉树的左子树
        
        return binary_root
    
    def encode_children(self, children):
        if not children:
            return None
        
        first_child = children[0]
        binary_node = TreeNode(first_child.val) # 第一个子节点成为二叉树的根节点
        binary_node.left = self.encode_children(first_child.children) # 递归地编码子节点的子树
        binary_node.right = self.encode_children(children[1:]) # 将其他子节点作为右子树
        
        return binary_node
    
    # Decodes your binary tree to an n-ary tree.
    def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':
        if data is None:
            return None
        
        n_ary_root = Node(data.val) # 创建N叉树的根节点
        n_ary_root.children = self.decode_children(data.left) # 解码二叉树的左子树以获取所有子节点
        
        return n_ary_root
    
    def decode_children(self, node):
        if node is None:
            return []
        
        n_ary_child = Node(node.val) # 创建子节点
        n_ary_child.children = self.decode_children(node.left) # 递归解码所有子节点
        siblings = self.decode_children(node.right) # 解码右子树以获取兄弟节点
        return [n_ary_child] + siblings
"""