二叉树距目标节点K距离节点求解（亚马逊SDE-2）代码异常排查

测试用例的序列化格式问题 #

标准二叉树层序序列化要求按层从左到右，给每个节点（包括空节点）固定的位置占位，不能跳位。你给的测试用例字符串1 N 2 N 3 N 4 5，构造完斜链结构后，缺少了层序末尾的空节点标记（比如节点4的右孩子、节点5的左右孩子的空值占位），严格来说是不规范的。不过靠现有buildTree的解析逻辑，这个字符串是可以正确解析出预期树结构的——也就是从节点5到节点1的路径长度为4，符合测试用例的预期输出，所以格式问题不是代码返回空的核心原因。

当前解法的核心逻辑缺陷 #

1. 图建模的设计存在硬伤
   把二叉树转无向图时，直接拿节点的数值data当图的唯一键，完全没有绑定树的实际节点对象。这种设计只要遇到树里有重复数值的节点，就会把不同节点的边混到同一个键下，把整个图结构搅乱。哪怕当前测试用例没有重复值，这种建模方式本身就不符合二叉树转图的基本要求。
2. 距离初始化存在边界漏洞
   初始化距离字典时，直接把图里所有键的距离默认设为0，没有显式标记目标节点的初始距离。如果目标节点因为图建模漏边没有被正确加入邻接表的键集合，BFS刚开始就会因为目标节点没有邻接边直接结束，最后自然返回空列表。
   对应到这个测试场景：如果makeGraph阶段漏掉了节点5的邻接边，那self.vertList[5]就是个空的默认列表，BFS从5出发找不到任何邻居，根本遍历不到4、3、2、1这些节点，最后结果自然是空。
3. BFS访问标记逻辑不严谨
   虽然入队时就标记已访问的流程本身没问题，但因为图建模是靠节点值而非节点对象，一旦键重复导致图结构混乱，已访问集合的标记也会跟着出错，直接打断遍历流程。

简单的修正方向 #

• 建模时不需要显式把整棵树转成邻接表，直接通过DFS记录每个节点的父节点映射，在原二叉树结构上就能做BFS计算距离，从根源上避免节点值重复的问题。
• 初始化距离字典时，把所有节点的距离默认设为无穷大，单独把目标节点的距离设为0，避免全0初始化带来的逻辑错误。
• 做访问标记时直接用节点对象当集合元素，不要用节点值，从根本上规避重复值带来的冲突。

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