javascript - JS深度优先遍历预序

Question

作为练习，我正在编写 JavaScript 来对二叉搜索树执行深度优先遍历的预排序。

注意:这是迭代，不是递归。我可以递归地完成它，但是 Python 中有一些方法可以迭代地完成它，所以我想看看这在 JS 中如何工作。

我的代码如下:

var preorderTraversal = function(root) {
    if(!root) return [];
    let stack = [root];
    let output = [];

    while(stack.length) {
        root = stack.shift();
        if(root !== null) {
            output.push(root.val);
            if(root.left !== null) stack.push(root.left);
            if(root.right !== null) stack.push(root.right); //Source of the issue
        }
    }

    return output;
};

假设输入是 [1,2,3] 这很好用。但是，当输入更多样化时会出现问题，例如[1,4,3,2]，它返回:

[1,4,3,2]

代替

[1,4,2,3]

因为当引擎碰到上面 block 中标记的代码行时，它会在右边迭代:

     1
    / \
   4   3
  /
 2

所以不知何故，您必须通知算法不断迭代每个左边，直到没有更多的左边，然后迭代右边。递归地，这非常简单。

但是使用迭代，没那么多。

令我感到奇怪的是，类似的 Python 函数会运行得很好:

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []

        stack, output = [root, ], []

        while stack:
            root = stack.pop()
            if root is not None:
                output.append(root.val)
                if root.right is not None:
                    stack.append(root.right)
                if root.left is not None:
                    stack.append(root.left)

        return output

显然，导致问题的语言存在差异，或者我在算法的某处犯了错误。

谁知道有什么区别？我更感兴趣的是了解原因，而不仅仅是让它发挥作用的捷径。

Answer 1

感谢评论中的帮助，这实际上是对 pop 与 shift 方法的简单误用。

Python 使用 pop 而我在 JS 中使用 shift。但这意味着我们必须颠倒我们找到正确值和左侧值的方向。

所以 JS 代码实际上是:

var preorderTraversal = function(root) {
    if(!root) return [];
    let stack = [root];
    let output = [];

    while(stack.length) {
        root = stack.pop();
        if(root !== null) {
            output.push(root.val);
            if(root.right !== null) stack.push(root.right);
            if(root.left !== null) stack.push(root.left);
        }
    }   

    return output;
}