var count = function(tree) {
var stack = [];
var count = 0;
for (var node = tree; node; count++, node = stack.pop()) {
if (node.left) stack.push(node.left);
if (node.right) stack.push(node.right);
}
return count;
};
上面的代码工作并返回二叉树中的节点数。
我很困惑这是如何工作的。不var stack = [];创建空数组？
如果是这样，在 for 循环中设置时 node 是否不会变为 0，从而使两个 if 语句都返回 false 并且不运行？
编辑：我刚刚意识到代码node = stack.pop()在循环体结束之前不会被执行。因此，直到该点的节点将包含传递到过程中的当前节点（从头节点开始）。
为这个平凡的问题道歉，我想该睡觉了
您可以将其重写为：
var count = function(tree) {
var stack = [];
var count = 0;
var node = tree; // set node to the tree (the tree's root node)
while (node) { // while the node is not null
// The way these pushes are done, it's basically doing a depth first search
if (node.left) stack.push(node.left);
if (node.right) stack.push(node.right);
count++;
node = stack.pop();
}
return count;
};
换句话说，node它在运行时不会变为零，因为它stack是空的。它设置为tree，而不是stack。你可以看到它在这里工作。
我提供了评论并创建了一个JS Fiddle。我希望这有帮助
var count = function(tree) {
// Stack is by default empty (empty array)
var stack = [];
var count = 0;
// Initially set node to the tree root. 'node' always points to the item being processed.
// Each node can have left and right children.
// They can be null as well.
// Comparison is to check if the 'node' is undefined or null
// count is incremented if a left or right children is found.
// stack.pop() removes the top most element from the array/stack.
for (var node = tree; node; count++, node = stack.pop()) {
// verify if left child exists, then push. This will add to the count when it is popped.
if (node.left) stack.push(node.left);
// verify if right child exists, then push. This will add to the count when it is popped.
if (node.right) stack.push(node.right);
}
return count;
};
// Count is a function that takes a binary tree, each node in the binary tree
// has a left and a right child. The tree itself is also such a note, namely
// the root node of the tree. What Count does with this tree is count the
// amount of nodes.
var count = function(tree) {
// We first create a new stack, which we plan to use for counting.
var stack = [];
// The initial count is zero.
var count = 0;
// Initial: We first take the root node.
// Condition: As long as node exists.
// Incrementation: We increment count, and take another node of the stack.
for (var node = tree; node; count++, node = stack.pop()) {
// For the current node, place it's left and right node on the stack.
if (node.left) stack.push(node.left);
if (node.right) stack.push(node.right);
}
// Remember: Init --> Body --> Incr --> Cond --> Body --> Incr --> Cond ...
// Now that all nodes have passed through the stack, return the count.
return count;
};
假设树是这样的：
1
/ \
2 3
/ \
4 5
事情是这样的：