作为练习,我正在编写 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
显然,导致问题的语言存在差异,或者我在算法的某处犯了错误。
谁知道有什么区别?我更感兴趣的是了解原因,而不仅仅是让它发挥作用的捷径。
最佳答案
感谢评论中的帮助,这实际上是对 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;
}
关于javascript - JS深度优先遍历预序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57777404/