树每层最左节点查找函数返回空数组问题排查

我编写了TreeNode类用于定义树节点，实现了findFirstNodes函数查找树每层的最左节点，并编写了测试代码。预期输出为[ 4, 3, 2 ]，但实际返回空数组，遍历过程中仅能打印到值为3的节点。我对树遍历有大致了解但细节生疏，希望解决该问题。

我的代码 #

TreeNode类定义 #

class TreeNode {
  constructor(value, left, right, level) {
    this.value = value;
    this.left = left;
    this.right = right;
    this.level = level
  }
}

查找每层最左节点的函数 #

function findFirstNodes(root) {

    const stack = [root];

    root.level = 0;
    const firsts = [];

    while (stack.length > 0) {

      const curr = stack.pop();

      if (firsts[curr.level]) {

          firsts.push(curr.value);

      };

      if (curr.left) {

          stack.unshift(curr.left);

      };

    };

    return firsts;

};

测试代码 #

const simpleTree = new TreeNode(4, null, null);
simpleTree.right = new TreeNode(8, null, null);
simpleTree.left = new TreeNode(3, null, null);
simpleTree.right.right = new TreeNode(2, null, null);

console.log(findFirstNodes(simpleTree)); // -> [ 4, 3, 2 ]

问题分析与修复 #

存在的问题 #

1. 遍历逻辑缺失：当前代码只处理节点的左子节点，完全忽略右子节点，导致树的右半部分（如值为8、2的节点）根本不会被遍历到。
2. 层级判断逻辑错误：if (firsts[curr.level])的判断完全搞反——我们需要在当前层级未记录最左节点时添加，应判断!firsts[curr.level]；且直接用push会导致数组索引混乱，需给firsts[curr.level]直接赋值。
3. 子节点层级未设置：仅给根节点设置了level=0，子节点的level属性未赋值，遍历子节点时curr.level为undefined，无法正确对应层级。
4. 遍历方式错误：找每层最左节点需要广度优先遍历（BFS）（按层级顺序处理节点），当前用stack.pop()+unshift的方式不符合BFS逻辑，应该用队列（先进先出）实现。

修复后的代码 #

function findFirstNodes(root) {
    // 用队列实现BFS，保证按层级顺序遍历
    const queue = [root];
    root.level = 0;
    const firsts = [];

    while (queue.length > 0) {
        const curr = queue.shift();

        // 当前层级无记录时，存入该层最左节点
        if (!firsts[curr.level]) {
            firsts[curr.level] = curr.value;
        }

        // 先左后右入队，保证每层从左到右遍历顺序
        if (curr.left) {
            curr.left.level = curr.level + 1;
            queue.push(curr.left);
        }
        if (curr.right) {
            curr.right.level = curr.level + 1;
            queue.push(curr.right);
        }
    }

    return firsts;
};

测试验证 #

运行原测试代码，现在会输出预期的[4, 3, 2]：

• 第0层最左节点是4
• 第1层最左节点是3
• 第2层最左节点是2（该层仅节点2）

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