不确定此片段的工作方式

Question

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循环中设置节点时不会变为0，从而使两个if语句返回false并且不会运行？

编辑：我刚刚意识到代码node = stack.pop()将不会执行，直到循环体的结束。因此，节点直到该点将包含传递给过程的当前节点（从头节点开始）。

道歉世俗的问题，它的时间睡觉，我认为

我提供意见，并创建了一个 JS Fiddle

Answer 1

你可以把它改写为：

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。 You can see it work here。

Answer 2

。我希望这有助于

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; 
}; 

Answer 3

// 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 

这是怎么一回事呢：

• 栈是空的，计数为0。
• 它开始“1”，它会在堆栈中添加子项“2”和“3”。
• 它增加了计数（0 - > 1），并采用堆栈的节点，即“2”。
• 继续“2”，它没有孩子。
• 它增加了计数（1 - > 2）并占用堆栈的一个节点，即“3”。
• 它继续“2”，它在堆栈上添加子项“4”和“5”。
• 它增加了计数（2 - > 3）并占用堆栈的一个节点，即“4”。
• 继续“4”，它没有孩子。
• 它增加了计数（3 - > 4）并获取堆栈的节点，即“5”。
• 继续“5”，它没有孩子。
• 它增加了计数（4 - > 5）并且不能占用堆栈的一个节点，它停止。
• 最终计数5被返回。