JS深度优先遍历预序

Question

作为练习，我正在编写 JavaScript 以在二叉搜索树上执行 Depth First Traversal 的 pre-order。

注意：这是迭代，不是递归。我可以递归地做，但是 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]，它returns:

[1,4,3,2]

而不是

[1,4,2,3]

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

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

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

令我感到奇怪的是，类似的 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;
}

JS深度优先遍历预序

JS Depth First Traversal Pre-Order

javascript

python

algorithm

depth-first-search