Python递归反序列化N叉树的指针变更问题咨询

作为Python新手，在实现N叉树反序列化功能时遇到指针变更问题：Java版本代码可通过所有测试用例，但Python版本出现子节点列表异常的情况。

输入与需求 #

• 输入：deserialize(String data)，示例字符串：[1[2][3[6][7[11[14]]]][4[8[12]]][5[9[13]][10]]]
• 字符串说明：1是N叉树的根节点，2、3、4、5是1的子节点；6是3的子节点；7是3的子节点，11是7的子节点，14是11的子节点；8是4的子节点，12是8的子节点；9、10是5的子节点，13是9的子节点。
• 需求：编写反序列化函数将字符串转换为Node对象。

Node类定义 #

class Node(object):
    def __init__(self, val=None, children=[]):
        self.val = val
        self.children = children

可行的Java代码 #

public Node deserialize(String data) {
    if(data == null || data.length() == 0) return null;
    return desedfs(data, 0, data.length());
}

private Node desedfs(String data, int st, int ed) {
    Node currRoot = new Node(Integer.MIN_VALUE, new ArrayList<>());
    for (int i = st+1 ; i < ed; ) {
        Character c = data.charAt(i);
        if(Character.isDigit(c)) {
            String s = "";
            while(Character.isDigit(data.charAt(i))) {
                s += Character.toString(data.charAt(i));
                i++;
            }
            currRoot = new Node(Integer.parseInt(s), new ArrayList<>());
        } else if(c == '[') {
            int rightindex = findpairpara(data,i);
            currRoot.children.add(desedfs(data, i, rightindex));
            i = rightindex;
        } else {
            i++;
        }
    }
    if(currRoot.val != Integer.MIN_VALUE) {
       return currRoot;
    }
    return null;
}

// Function to find the matching bracket. For example, in "[[12]]"
// If left index is 0, then return index is 5.If left index is 1, then return index is 4
private int findpairpara(String s, int leftindex) {
    int cnt = 0;
    for (int i = leftindex; i < s.length(); i++) {
        Character c = s.charAt(i);
        if (c == '[') {
            cnt++;
        } else if (c == ']') {
            cnt --;
        }
        if (cnt == 0) {
            return i;
        }
    }
    return -1;
}

出现问题的Python代码 #

def getmatch(self, data, idx):
    cnt = 0
    for i in range(idx, len(data)):
        if data[i] == "[":
            cnt += 1
        if data[i] == "]":
            cnt -= 1
        if cnt == 0:
            return i
    return -1

def deserializef(self, data, st, end):
    currnum = 0
    p = st+1
    root = Node(-1, [])
    while p < end:
        while data[p].isdigit():
            currnum = currnum * 10 + int(data[p])
            p += 1
            root = Node(currnum, [])
        if data[p] == "[":
            matchingidx = self.getmatch(data, p)
            c = self.deserializef(data, p, matchingidx)
            root.children.append(c)
            p = matchingidx
        if data[p] == "]":
            p += 1
    return root

问题现象：返回的根节点1的children列表为空；打印root.children的id发现，给父节点3添加子节点6时的列表id，和添加子节点7时的id不同，最终3的children列表长度应为2但实际为1。

修改后可行的Python代码 #

def deserializef(self, data, st, end):
    currnum = 0
    p = st+1
    children = []
    while p < end:
        while data[p].isdigit():
            currnum = currnum * 10 + int(data[p])
            p += 1
        if data[p] == "[":
            matchingidx = self.getmatch(data, p)
            c = self.deserializef(data, p, matchingidx)
            children.append(c)
            p = matchingidx
        if data[p] == "]":
            p += 1
    return Node(currnum, children)

问题解析 #

原Python代码错误原因 #

原代码的核心问题在于变量覆盖导致子节点添加到错误的对象上：

1. 初始化root = Node(-1, [])后，在数字解析的内层while循环中，每次解析数字都会创建新的Node(currnum, [])并赋值给root。比如解析完节点3后，继续解析到节点7时，root会被替换成指向节点7的新对象。
2. 后续处理[时，给root.children添加子节点，此时操作的是节点7的children列表，而不是之前的节点3的列表。但节点3并没有被正确关联这个7子节点，因为root已经不再指向节点3了，最终导致节点3的children只保留了第一个子节点6，而节点7的子节点被添加到了错误的地方，根节点1的children也因为后续的变量覆盖丢失了所有子节点。

修改后代码可行的原因 #

修改后的代码把子节点列表和当前节点的创建解耦：

1. 用单独的children列表变量维护当前节点的所有子节点，不管后续解析多少数字，子节点都添加到这个固定的列表中，不会因为创建新节点而丢失之前的子节点引用。
2. 最后统一用解析完成的currnum和收集好的children创建Node对象返回，确保每个节点的子节点列表都是完整的。

Java与Python代码的差异 #

Java代码中虽然也会重新赋值currRoot，但Java的for循环逻辑是每次迭代处理一个独立的元素：解析数字后创建新节点，后续的括号处理只会针对这个新节点添加子节点，处理完后i跳到括号末尾，下一次循环处理下一个元素（比如下一个[），不会出现Python代码中同一个while循环里多次覆盖root的情况。Python的while循环逻辑没有区分开“当前节点创建”和“子节点添加”的边界，导致变量覆盖后子节点添加到了错误对象。

内容的提问来源于stack exchange，提问作者erinnnn