如何基于带层级的前序遍历构建N叉树并修正代码问题

给定包含N叉树前序遍历结果的JSON响应，其中TONODES数组是前序节点集合，每个节点包含Hierlevel层级属性，需要将其转换为指定的嵌套树形JSON结构。

采用栈结构实现时遇到问题：无法正确跟踪父节点的嵌套路径，例如层级0(N0)→1(N1)→2(N2)的场景中，N2无法被正确添加至N1的子节点下，而是错误地直接对N1进行操作。

输入JSON示例 #

{
  "ControllingArea" : "TZUS",
  "TopNodes" : false,
  "Language" : "EN",
  "TONODES" : [
    {
      "Groupname" : "INC",
      "Hierlevel" : 0,
      "Valcount" : 0,
      "Descript" : "INC"
    },
    {
      "Groupname" : "INC-BBSR",
      "Hierlevel" : 1,
      "Valcount" : 0,
      "Descript" : "INC1"
    },
    {
      "Groupname" : "INC-STPI",
      "Hierlevel" : 2,
      "Valcount" : 0,
      "Descript" : "INC2"
    },
    {
      "Groupname" : "INC-FORT",
      "Hierlevel" : 2,
      "Valcount" : 0,
      "Descript" : "INC3"
    },
    {
      "Groupname" : "INC-BBL",
      "Hierlevel" : 1,
      "Valcount" : 0,
      "Descript" : "INC4"
    },
    {
      "Groupname" : "INC-PUNE",
      "Hierlevel" : 1,
      "Valcount" : 0,
      "Descript" : "INC5"
    }
  ],
  "TOVALUE" : [
    {
      "Valfrom" : "",
      "Valto" : ""
    }
  ]
}

期望输出JSON示例 #

{
    "INC": {
        "Groupname": "INC",
        "Hierlevel": 0,
        "Valcount": 0,
        "Descript": "INC",
        "INC-BBSR": {
            "Groupname": "INC-BBSR",
            "Hierlevel": 1,
            "Valcount": 0,
            "Descript": "INC1",
            "INC-STPI": {
                "Groupname": "INC-STPI",
                "Hierlevel": 2,
                "Valcount": 0,
                "Descript": "INC2"
            },
            "INC-FORT": {
                "Groupname": "INC-FORT",
                "Hierlevel": 2,
                "Valcount": 0,
                "Descript": "INC3"
            }
        },
        "INC-BBL": {
            "Groupname": "INC-BBL",
            "Hierlevel": 1,
            "Valcount": 0,
            "Descript": "INC4"
        },
        "INC-PUNE": {
            "Groupname": "INC-PUNE",
            "Hierlevel": 1,
            "Valcount": 0,
            "Descript": "INC5"
        }
    }
}

错误原因 #

原代码的核心问题是：每次添加子节点时，都是从根response对象中获取父节点，而非跟踪当前嵌套路径中的父节点引用。比如处理层级2的节点时，应该直接往层级1的节点对象中添加子节点，但原代码却从根对象中重新取层级1节点，逻辑上没有正确维护当前的嵌套上下文，当层级结构复杂时会出错。

修正后的Java代码 #

@Override
public ResponseDTO getTreeStructure(JSONObject sapResponse) {
    JSONObject response = new JSONObject();
    // 栈中存储当前可添加子节点的父节点对象，维护嵌套路径
    Stack<JSONObject> parentStack = new Stack<>();

    JSONArray nodes = sapResponse.getJSONArray("TONODES");
    for (int i = 0; i < nodes.length(); i++) {
        JSONObject currentNode = nodes.getJSONObject(i);
        String groupName = currentNode.getString("Groupname");
        int currentLevel = currentNode.getInt("Hierlevel");

        if (parentStack.isEmpty()) {
            // 根节点直接加入响应根对象
            response.put(groupName, currentNode);
            parentStack.push(currentNode);
        } else {
            // 找到层级小于当前节点的父节点
            while (!parentStack.isEmpty() && parentStack.peek().getInt("Hierlevel") >= currentLevel) {
                parentStack.pop();
            }
            // 往父节点中添加当前子节点
            parentStack.peek().put(groupName, currentNode);
            parentStack.push(currentNode);
        }
    }

    return new ResponseDTO(200, "ok", response);
}

代码逻辑说明 #

1. 栈的作用：栈中存储的是当前层级的父节点对象，而非仅节点数据，直接跟踪嵌套路径，确保子节点被添加到正确的父节点下。
2. 根节点处理：栈为空时，当前节点是根节点，直接加入响应根对象并入栈。
3. 子节点处理：
   • 若当前节点层级高于栈顶节点，栈顶即为父节点，直接添加子节点并入栈当前节点。
   • 若当前节点层级低于或等于栈顶节点，循环出栈直到找到层级小于当前节点的父节点，再添加子节点并入栈当前节点。

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