这是我设置树节点的代码。
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 的那个。
有几个问题:
条件
firsts[curr.level]
不会为真,因为firsts
为空。唯一可以使该数组非空的地方是在这个 if
块内,这意味着它永远不会发生。 firsts
将永远保持空虚。
显然您想在节点实例中存储节点的级别。虽然这不是必需的,但您只需对一个节点执行此操作:根节点。它的级别为 0。代码中没有其他级别值出现,并且没有其他节点获得分配给它的级别。
您的代码永远不会访问节点的
right
属性,乍一看这似乎是合理的(因为您正在寻找每个级别上最左边的节点),但级别上最左边的节点很可能是其父节点的右子节点,或者它的父母可能是一个正确的孩子,...等等。事实上,您的测试代码创建了一棵树,该树在底层只有一个节点(值为 2),并且它是右子节点。所以你不能排除右侧子节点。
不是一个真正的问题,但命名你的数组
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 ]