在树的每一层中查找最左边的节点

Question

这是我设置树节点的代码。

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 ]

这就是树的外观。

//        5
//       / \
//      4   7
//     / \   \
//    1   3   2
//       /    / \
//      8    4   9
//              / \
//             2   4

// Expected Output -> [ 5, 4, 1, 8, 2 ]

但是我的结果数组是空的。

对于如何遍历树木之类的知识我已经大致掌握了，但是很多细节对我来说还是生疏的。该代码不会导致任何错误，但数组只是空的。我尝试在遍历树时控制台记录 curr 变量，但我只得到 3 的那个。

Answer 1

有几个问题：

• 条件

  firsts[curr.level]

  不会为真，因为

  firsts

  为空。唯一可以使该数组非空的地方是在这个

  if

  块内，这意味着它永远不会发生。

  firsts

  将永远保持空虚。

• 显然您想在节点实例中存储节点的级别。虽然这不是必需的，但您只需对一个节点执行此操作：根节点。它的级别为 0。代码中没有其他级别值出现，并且没有其他节点获得分配给它的级别。

• 您的代码永远不会访问节点的

  right

  属性，乍一看这似乎是合理的（因为您正在寻找每个级别上最左边的节点），但级别上最左边的节点很可能是其父节点的右子节点，或者它的父母可能是一个正确的孩子，...等等。事实上，您的测试代码创建了一棵树，该树在底层只有一个节点（值为 2），并且它是右子节点。所以你不能排除右侧子节点。

• 您问题的标题表明您的输入将是标准树。然而，您的

  TreeNode

  类仅为二叉树设计。

不是一个真正的问题，但命名你的数组

stack

会产生误导，因为你将它用作队列，而不是堆栈。

用队列来解决这个问题的想法很好。但是因为

unsift

的时间复杂度很差，我建议使用两个（嵌套）循环：一个循环迭代已访问过的最后一层中的节点，另一个循环访问这些节点的所有直接子节点并将它们放入在一个新数组中：这将包含下一级的所有节点。完成后，该数组可以再次成为外循环中使用的源。这样就可以很容易地识别每个级别上的第一个节点。

这是建议的代码：

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

function findFirstNodes(root) {
    let levelNodes = [root];

    const firsts = [];
    while (levelNodes.length > 0) {
        firsts.push(levelNodes[0].value);
        const nextLevelNodes = [];
        for (const node of levelNodes) {
            if (node.left) nextLevelNodes.push(node.left);
            if (node.right) nextLevelNodes.push(node.right);
        }
        levelNodes = nextLevelNodes;
    }
    return firsts;
}

// Your test case:
const simpleTree = new TreeNode(4,
    new TreeNode(3),
    new TreeNode(8,
        null,
        new TreeNode(2)
    )
);

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

要对任何有根树（而不仅仅是二叉树）执行相同的操作，您需要以不同的方式定义

TreeNode

类，并停止使用

left

和

right

。

class TreeNode {
    constructor(value, ...children) {
        this.value = value;
        this.children = children;
    }
}

function findFirstNodes(root) {
    let levelNodes = [root];

    const firsts = [];
    while (levelNodes.length > 0) {
        firsts.push(levelNodes[0].value);
        levelNodes = levelNodes.flatMap(node => node.children);
    }
    return firsts;
}

// Your test case. Note that now the node with value 2 is "just" 
//    THE child, not specifically a "right" child.
const simpleTree = new TreeNode(4,
    new TreeNode(3),
    new TreeNode(8,
        new TreeNode(2)
    )
);

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