深度优先遍历

• 深度优先遍历通过「栈」实现；
• 深度优先遍历符合「后进先出」规律，可以借助「栈」实现；
• 深度优先遍历有明显的「递归」结构，递归也是借助「栈」实现的，因此深度优先遍历一般通过「递归」实现，底层借助了「栈」这个数据结构作为支持；

比较递归与非递归实现：

	递归	非递归
优点	编码容易、可读性强、易于维护	执行效率较高
缺点	递归方法逐层调用函数会产生一定性能消耗，如果递归深度较深，可能会抛出 StackOverflow 异常	不是所有的递归都可以很容易地通过模拟栈来实现。显式编写栈的代码较难理解，不易于维护

实现

二叉树

• 前序遍历
• 中序遍历
• 后序遍历

N 叉树遍历：

• 前序遍历
• 后序遍历

应用

• 求根到叶子节点数字之和
• 无向图中连通分量的数目
• 检测图中是否存在环
  • 冗余连接
  • 找到最终的安全状态