深度优先遍历非递归算法

深度优先遍历（Depth First Search, DFS）是一种用于遍历或搜索树或图的算法。DFS从根节点开始，沿着一个分支一直遍历到底，直到无法继续为止，然后回溯到前一个节点，再按照另一个分支继续遍历。DFS有递归和非递归两种实现方式，其中非递归方式相对递归方式更能节省空间。本文将重点介绍深度优先遍历的非递归算法实现及其优缺点。

1. 非递归算法实现

深度优先遍历非递归算法实现的核心思想是借助栈来实现。具体可以按照如下步骤：

1. 将根节点压入栈中。

2. 循环执行以下步骤直至栈为空：

1）弹出栈顶节点；

2）将该节点的孩子节点按相反的顺序依次压入栈中。

以下是Python实现代码：

```python

def dfs_iterative(root):

if not root:

return []

res, stack = [], [root]

while stack:

cur = stack.pop()

res.append(cur.val)

if cur.right:

stack.append(cur.right)

if cur.left:

stack.append(cur.left)

return res

```

2. 优缺点分析

2.1 优点

（1）相对递归方式，非递归方式能够节省堆栈空间，避免由于递归深度过大而导致堆栈溢出。

（2）非递归方式能够较好地实现树或图的遍历，对于某些复杂结构的树或图，仍能快速地完成搜索。

2.2 缺点

（1）相对于递归方式，非递归方式需要更多的代码实现，且容易出错。

（2）非递归方式的实现较为繁琐，可能会降低代码执行的速度。

3.