javascript - JS深度优先遍历预购

问题描述

就像练习一样，我正在编写 JavaScript 来pre-order在Depth First Traversal二叉搜索树上进行操作。

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

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

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

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

对我来说奇怪的是，一个类似的 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

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

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

标签： javascriptpythonalgorithmdepth-first-search

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

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

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

javascript - JS深度优先遍历预购

问题描述

解决方案

推荐阅读