0431：将 N 叉树编码为二叉树（★★）

2016-03-06 约 409 字预计阅读 1 分钟次阅读

力扣第 431 题

题目

设计一个算法，可以将 N 叉树编码为二叉树，并能将该二叉树解码为原 N 叉树。一个 N 叉树是指每个节点都有不超过 N 个孩子节点的有根树。类似地，一个二叉树是指每个节点都有不超过 2 个孩子节点的有根树。你的编码 / 解码的算法的实现没有限制，你只需要保证一个 N 叉树可以编码为二叉树且该二叉树可以解码回原始 N 叉树即可。

例如，你可以将下面的 3-叉 树以该种方式编码：

注意，上面的方法仅仅是一个例子，可能可行也可能不可行。你没有必要遵循这种形式转化，你可以自己创造和实现不同的方法。

注意：

N 的范围在 [1, 1000]
不要使用类成员 / 全局变量 / 静态变量来存储状态。你的编码和解码算法应是无状态的。

分析

关键是如何保存孩子个数的信息，一种想法是将后面的孩子依此接到第一个孩子右边。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Codec:
    def encode(self, root: 'Node') -> TreeNode:
        if not root:
            return None
        node = TreeNode(root.val)
        if root.children:
            p = node.left = self.encode(root.children[0])
            for chi in root.children[1:]:
                p.right = self.encode(chi)
                p = p.right
        return node
        
    def decode(self, data: TreeNode) -> 'Node':
        if not data:
            return None
        node = Node(data.val, [])
        p = data.left
        while p:
            node.children.append(self.decode(p))
            p = p.right
        return node

64 ms

目录

0431：将 N 叉树编码为二叉树（★★）

题目

分析

解答