当前位置：首页 > web >正文

行政区划编码树形题解

web 2025/9/7 11:11:12

行政区划编码树形题解

题目描述

将一维的中国行政区划编码数组转换为树形结构，处理直辖市等特殊层级跳跃情况。

输入数据特点

const codes = [// === 北京市（直辖市，省级） ==={code: "110000",name: "北京市",},{code: "110101",name: "东城区",},{code: "110102",name: "西城区",},{code: "110105",name: "朝阳区",},{code: "110106",name: "丰台区",},{code: "110107",name: "石景山区",},{code: "110108",name: "海淀区",},{code: "110109",name: "门头沟区",},{code: "310000",name: "上海市",},{code: "310101",name: "黄浦区",},{code: "310104",name: "徐汇区",},{code: "310105",name: "长宁区",},{code: "310106",name: "静安区",},{code: "310107",name: "普陀区",},{code: "310109",name: "虹口区",},{code: "310110",name: "杨浦区",},// === 河北省（普通省份，省 → 市 → 区） ==={code: "130000",name: "河北省",},{code: "130100",name: "石家庄市",},{code: "130102",name: "长安区",},{code: "130104",name: "桥西区",},{code: "130200",name: "唐山市",},{code: "130202",name: "路北区",},{code: "130203",name: "路南区",},
];

数据规律分析

编码规则：

xx0000：省级/直辖市级（如110000北京市、130000河北省）
xx0100：市级（如130100石家庄市）
xx0101：区县级（如130102长安区）

特殊情况：

直辖市跳层：110000北京市 → 110101东城区（跳过了市级）
标准层级：130000河北省 → 130100石家庄市 → 130102长安区

预期输出结构

转换后应该得到如下树形结构：

[{"code": "110000","name": "北京市","children": [{"code": "110101", "name": "东城区"},{"code": "110102", "name": "西城区"},{"code": "110105", "name": "朝阳区"},{"code": "110106", "name": "丰台区"},{"code": "110107", "name": "石景山区"},{"code": "110108", "name": "海淀区"},{"code": "110109", "name": "门头沟区"}]},{"code": "310000","name": "上海市","children": [{"code": "310101", "name": "黄浦区"},{"code": "310104", "name": "徐汇区"},{"code": "310105", "name": "长宁区"},{"code": "310106", "name": "静安区"},{"code": "310107", "name": "普陀区"},{"code": "310109", "name": "虹口区"},{"code": "310110", "name": "杨浦区"}]},{"code": "130000","name": "河北省","children": [{"code": "130100","name": "石家庄市","children": [{"code": "130102", "name": "长安区"},{"code": "130104", "name": "桥西区"}]},{"code": "130200","name": "唐山市","children": [{"code": "130202", "name": "路北区"},{"code": "130203", "name": "路南区"}]}]}
]

算法核心挑战

父子关系识别：根据编码规律找到每个节点的父节点
跳层处理：直辖市的区直接隶属于直辖市，跳过市级
缺失层级处理：当直接父节点不存在时，需要向上查找

解决方案一：本人事后实现（略显丑陋）

// 下面是本人事后写的代码  有点烂说是哈
const roots = [];
const getParent = (code) => {switch (true) {case code.endsWith("0000"):return null;case code.endsWith("00"):return code.slice(0, 2) + "0000";default:return code.slice(0, 4) + "00";}
};const codeMap = new Map(codes.map((value) => [value.code, value]));for (let element of codes) {const { code } = element;const node = codeMap.get(code);const pcode = getParent(code);if (pcode === null) {roots.push(node);} else {if (codeMap.has(pcode)) {const pnode = codeMap.get(pcode);const pnodeChildren = pnode?.children;Array.isArray(pnodeChildren)? pnodeChildren.push(node): (pnode.children = [node]);} else {let gcode = getParent(pcode);const gnode = codeMap.get(gcode);const gnodeChildren = gnode?.children;Array.isArray(gnodeChildren)? gnodeChildren.push(node): (gnode.children = [node]);}}
}console.log(JSON.stringify(roots));

算法分析

优点：

直接处理跳层情况，当直接父节点不存在时，查找祖父节点
使用Map提高查找效率
逻辑相对直观

缺点：

只能处理跳一层的情况，如果跳多层会有问题
代码相对冗长，有重复逻辑
children数组初始化逻辑复杂

解决方案二：GPT优化版本

// GPT优化后  其实我们无需判断这个垃圾的
const removeEmptyArray = (array) => {for (let element of array) {if (element.children.length === 0) {delete element.children;} else {removeEmptyArray(element.children);}}
};const buildTree = () => {const map = new Map(codes.map((value) => [value.code, { ...value, children: [] }]));const roots = [];for (let code of map.values()) {const codeString = code.code;let pcode = getParent(codeString);while (pcode && !map.has(pcode)) {pcode = getParent(pcode); //一直往上面找就完了}if (pcode === null) {roots.push(code);} else {const pnode = map.get(pcode);pnode.children.push(code);}}removeEmptyArray(roots);return JSON.stringify(roots);
};console.log("GPT优化的代码", buildTree());

优化亮点

改进之处：

通用的跳层处理：使用while循环一直向上查找，可以处理任意层级的跳跃
预初始化children：所有节点预先创建空的children数组，避免条件判断
统一的处理逻辑：不需要区分是否存在父节点的情况
清理空数组：最后移除空的children属性，保持输出干净

核心改进：

// 原版：只能跳一层
if (codeMap.has(pcode)) {// 处理直接父节点
} else {let gcode = getParent(pcode); // 只处理祖父节点// ...
}// 优化版：可以跳任意层
while (pcode && !map.has(pcode)) {pcode = getParent(pcode); // 一直往上找
}