基于链表与树结构优化Lee算法求解迷宫的实现问题咨询

思路完全可行 #

你的方案本质是基于BFS的最短路径树实现，完全能达成需求：

• 用树结构记录节点邻接关系+父节点指针，本身就是BFS求最短路径的标准逻辑——BFS遍历过程中天然会构建一棵以起点为根、终点为叶的最短路径树，通过父节点反向回溯就能直接得到最短路径，彻底消除回溯操作
• 链表存储最短路径只是路径的输出形式，只要树的父节点链正确，就能从终点反向遍历到起点，再转为正向链表即可

段错误与代码失效的常见原因 #

段错误的核心诱因 #

• 内存越界访问：比如访问迷宫数组时行列索引超出范围，或是未初始化树/链表节点指针就直接解引用
• 内存管理混乱：动态分配的节点（树节点、链表节点）未正确释放，或是重复释放同一指针，导致野指针
• 父节点指针非法赋值：比如将节点的父节点指向自身，或是指向迷宫外的无效坐标

可运行但无法完成任务的问题点 #

• BFS遍历逻辑漏洞：未标记已访问节点导致重复入队，或是遗漏了部分方向的邻接节点（比如只处理上下，没处理左右）
• 最短路径树构建失败：找到终点后未及时终止遍历，或是父节点指针未正确关联到上一层的有效节点
• 路径还原逻辑错误：从终点回溯父节点时中断，或是链表构建时顺序颠倒（把终点作为链表头，未反转成起点到终点的顺序）

快速调试建议 #

• 打印每个入队节点的坐标和对应父节点坐标，验证树结构的正确性
• 检查迷宫边界判断代码，确保row和col始终在合法范围内
• 强制每个节点入队前标记为已访问，避免重复处理
• 先手动从终点回溯父节点并打印路径，确认能回到起点后再构建链表

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