428. Serialize and Deserialize N-ary Tree 反序列化后无法回到原树结构。。。。。。

下方代码能够运行成功。举个例子，就以一个二叉树为例，[1, 2, 3, null, null, null, null]。按照下方代码序列化后，返回的字符串是"12###3###"，这里我假设2和3的孩子都是二叉树。然后我按照下方的反序列化代码挨步分析，发现代码运行到第二个#就结束了，输出的结果是[1, 2]。可是下方代码确运行成功了。。。。。。

下面是我的反序列化步骤分析：
1: node是1，儿子是[]。child = 进入下一步dfs；
2: node是2，儿子是[]。child = 进入下一步dfs；
第一个#：返回None给到上一层；
回到2: 此时child = None，发现不进while循环，然后输出node，该层结束。返回2这个node给到1层的child；
回到1: 此时child = node2。进入while循环，node1的儿子列表加入2这个儿子，然后child = 下一个dfs；
第二个#：返回None给到上一层；
回到1: 此时child = None，发现不会再进行while循环了。退出循环，输出node1这个节点。
整个过程结束，最终返回[1, 2]。字符串后面还一堆#3###，都不执行了。

这个代码运行通过了，请问我上面的步骤分析问题出在哪？？？？？想了半天，谢谢！！！！

"""

# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
class Codec:
    def serialize(self, root: 'Node') -> str:
        """Encodes a tree to a single string.
        :type root: Node
        :rtype: str
        """
        def dfs(root):
            if not root:
                result.append("#")
            else:
                result.append(str(root.val))
                for child in root.children:
                    dfs(child)
                result.append("#")
        result = []
        dfs(root)
        return " ".join(result)


    def deserialize(self, data: str) -> 'Node':
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: Node
        """
        def dfs():
            val = next(data)
            if val == "#":
                return None
            node = Node(int(val), [])
            child = dfs()
            while child:
                node.children.append(child)
                child = dfs()
            return node
        data = iter(data.split())
        return dfs()

ATPtennis 发表于 2021-9-5 06:45
最后一个疑问，二叉树里，dfs我们经常这么做，比如
if not node:
       return None

不是，这个取决于它树的定义，二叉树每个node都规定有left and right, 所以即使没有left,你也可以access left然后发现是None.

N叉树的时候你也没有办法dfs(node.left) dfs(node.right)因为儿子是用一个list呈现的。

这道题的N叉树的定义它的儿子们是一个list,这个list里只有有value的儿子。
如果你重新定义一下N叉树，你说这个儿子list里面必须有N个元素，有儿子放儿子没儿子放None. 那么比如一个4叉数，应该有4个儿子，但是只有中间两个，那就是 [None, 儿子, 儿子, None],这样的话就会出现你说的在儿子里读到None.

然而这个题对N叉数的定义里面就只有[儿子，儿子], 因为存None在儿子里没有什么意义，不影响serialize和deserialize。

你的树应该是这样的吧   
    1
   /  \
  2   3
这个树按底下的serialize跑出来应该是 1 2 # 3 # #

cloudero 发表于 2021-09-04 15:19:32
你的树应该是这样的吧   
    1
   /  \

可是在for循环里面，孩子找到none我写的是返回#。你的意思是2这个节点，往下就不进for循环了吗

cloudero 发表于 2021-09-04 15:19:32
你的树应该是这样的吧   
    1
   /  \

即便root.children是None，那个for循环也会运行，然后进dfs，然后返回#，不是这样吗

ATPtennis 发表于 2021-9-4 19:52
即便root.children是None，那个for循环也会运行，然后进dfs，然后返回#，不是这样吗

None不会在children里，children里的Node都是有内容的儿子。你可以随便搞个test run一下print一下儿子们，你就能看到儿子里没有None。

cloudero 发表于 2021-9-5 03:00
None不会在children里，children里的Node都是有内容的儿子。你可以随便搞个test run一下print一下儿子们 ...

最后一个疑问，二叉树里，dfs我们经常这么做，比如
if not node:
       return None
dfs(node.left)
dfs(node.right)
这时候如果一个结点是叶子结点，它会继续运行dfs，然后在下一层的时候，它会返回None。
N叉树的时候，我们将
dfs(node.left)
dfs(node.right)
改成了一个for循环，那么这时候情况就变成了，如果当前是叶子结点，那么压根不会进入dfs了，和二叉树情况完全不同。二叉树是需要再进去，再判断。是这样理解吗？

cloudero 发表于 2021-9-5 18:04
不是，这个取决于它树的定义，二叉树每个node都规定有left and right, 所以即使没有left,你也可以access  ...

谢谢解惑！！！这下清楚了！！！！

cloudero 发表于 2021-9-5 03:00
None不会在children里，children里的Node都是有内容的儿子。你可以随便搞个test run一下print一下儿子们 ...

老哥，受累再看一下我最新发的帖子，那道题我那个代码，检查了两天了，不知道哪里有问题，真心希望能解惑！！！！谢谢！！那道题是个难题。