非递归深度优先搜索(DFS)算法是一种遍历或搜索树或图的算法。与递归DFS相比,非递归DFS使用显式的栈来存储待访问的节点,而不是依赖函数调用栈。这样可以避免递归调用的开销,并且在某些情况下可以更好地控制栈的深度。
以下是非递归DFS算法的基本步骤:
以下是一个使用非递归DFS遍历二叉树的示例(假设树节点具有value
、left
和right
属性):
def dfs_iterative(root):
if not root:
return
stack = [root]
while stack:
node = stack.pop()
print(node.value) # 访问节点
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
# 示例用法
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
dfs_iterative(root)
这个示例中,我们使用一个栈来存储待访问的节点。我们从根节点开始,将其压入栈中。然后,我们不断弹出栈顶节点并访问它,同时将其未访问的邻居节点压入栈中。这个过程一直持续到栈为空。
领取专属 10元无门槛券
手把手带您无忧上云