如何遍历非二叉树结构的国际象棋棋盘节点？

你的核心问题是递归创建棋盘节点时重复生成了大量相同坐标的Node，导致遍历得到的节点数远超过8x8棋盘应有的64个。

问题根源 #

当前buildBoard的递归逻辑存在重复创建：比如创建(1,1)节点时会生成右侧的(2,1)，创建(2,1)时又会生成上方的(2,2)；而创建(1,1)的上方(1,2)时，又会再次生成右侧的(2,2)——同一个坐标的节点被多次重复创建，最终节点数呈指数级增长。

修正方案：用缓存避免重复创建 #

我们需要一个缓存容器记录已创建的节点，确保每个(x,y)坐标只生成一次Node，同时补全节点间的反向关联（比如右侧节点的left指向当前节点，上方节点的bottom指向当前节点）。

修正后的完整代码

function Node(pos, top = null, right = null, left = null, bottom = null) {
  this.pos = pos;
  this.top = top;
  this.right = right;
  this.left = left;
  this.bottom = bottom;
}

function buildBoard() {
  // 二维数组缓存已创建的节点，索引对应棋盘1-8的坐标
  const nodeCache = Array.from({ length: 9 }, () => Array(9).fill(null));

  function createNode(x, y) {
    // 超出棋盘范围直接返回null
    if (x < 1 || x > 8 || y < 1 || y > 8) return null;
    // 已创建过该坐标的节点，直接返回缓存的实例
    if (nodeCache[x][y]) return nodeCache[x][y];

    const currentNode = new Node([x, y]);
    nodeCache[x][y] = currentNode; // 存入缓存，避免后续重复创建

    // 关联右侧节点，并设置右侧节点的left指向当前节点
    currentNode.right = createNode(x + 1, y);
    if (currentNode.right) currentNode.right.left = currentNode;

    // 关联上方节点，并设置上方节点的bottom指向当前节点
    currentNode.top = createNode(x, y + 1);
    if (currentNode.top) currentNode.top.bottom = currentNode;

    return currentNode;
  }

  // 从棋盘左下角(1,1)开始创建，返回根节点
  return createNode(1, 1);
}

验证遍历结果 #

可以用以下函数收集所有节点，确认数量为64：

function collectAllNodes(root) {
  const nodeSet = new Set();
  function traverse(node) {
    if (!node || nodeSet.has(node)) return;
    nodeSet.add(node);
    traverse(node.top);
    traverse(node.right);
    traverse(node.left);
    traverse(node.bottom);
  }
  traverse(root);
  return Array.from(nodeSet);
}

const chessBoard = buildBoard();
const allNodes = collectAllNodes(chessBoard);
console.log(allNodes.length); // 输出64，符合预期

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