Question

二叉树的深度遍历和广度遍历

Answer 1

沿着树的深度遍历结点，尽可能深的搜索树的分支。如果当前的节点所在的边都被搜索过，就回溯到当前节点所在的那条边的起始节点。一直重复直到进行到发现源节点所有可达的节点为止。

因为深度优先搜索算法是先访问根节点，接着遍历左子树再遍历右子树。为了方便，我们可以引入 堆栈 这个数据结构来帮我们快速解决DFS算法。因为栈是 后进先出 的结构，所以我们可以先将 右子树压栈，再将左子树压栈 ，这样左子树就位于栈顶，可以保证先遍历左子树再遍历右子树。

我们通过下面的这个二叉树来简单的画图实现栈的深度优先搜索

当我们在压栈时，必须确保该节点的左右子树都为空，如果不为空就需要先将它的右子树压栈，再将左子树压栈。等左右子树都压栈之后，才将结点压栈。

解决方案

从根节点开始，沿着树的宽度遍历树的节点，直到所有节点都被遍历完为止。

因为是按照一层一层遍历的，所以我们考虑引入 队列 这个数据结构帮助我们实现广度优先搜索算法。

给出一棵二叉树，返回其节点值 从底向上 的层次序遍历
解决方法：和上面的实现方式类似，只是最后需要把容器翻转过来。