二叉树: DFS 递归和迭代
时间: 2023-11-12 13:04:42 浏览: 126
二叉树的深度优先搜索(DFS)可以使用递归和迭代两种方式实现。递归方式是通过递归函数来完成的,而迭代方式则是利用栈(或者使用队列也可以)来模拟递归的过程。
递归实现DFS的过程如下:
1. 如果节点为空,返回。
2. 首先访问当前节点。
3. 递归访问当前节点的左子树。
4. 递归访问当前节点的右子树。
迭代实现DFS的过程如下:
1. 如果根节点为空,返回。
2. 创建一个栈,并将根节点入栈。
3. 当栈不为空时,执行以下操作:
- 弹出栈顶节点,并访问该节点。
- 如果该节点的右子节点不为空,将右子节点入栈。
- 如果该节点的左子节点不为空,将左子节点入栈。
这样,我们可以通过递归或迭代的方式来实现二叉树的深度优先搜索。
阅读全文
相关推荐








