先序的非递归实现可以用队列实现么？

Question

先序遍历非递归，只是需要一个数据结构将左右子树的节点进行存储，并按照一定顺序进行遍历，按照我的理解，只要有能存储2个数据的数据结构都可以进行非递归。但是广度优先遍历，就必须采用排队的形式，不然无法保证同一层级排列在一起。

Answer 1

liuyubobobo 2020-06-10 05:01:30

先序遍历无法只使用一个队列实现。或者你的想法是怎样的？实际用代码试试看？

但是由于我们其实可以使用队列包装出栈的功能，所以广义上说，说我们能用队列实现先序遍历也没有错。

关于使用队列实现栈，可以参考这里：https://leetcode-cn.com/problems/implement-stack-using-queues/

继续加油！：）

• 提问者 qq_萌新_4 #1

  只需要把栈的push操作顺序反过来就行了啊，先存左边再存右边
  Queue<Node> q = new LinkedList<>();
          q.add(root);
          while (!q.isEmpty()) {
              Node cur = q.remove();
              System.out.println(cur.e);
              if (cur.left != null) {
                  q.add(cur.left);
              }
              if (cur.right != null) {
                  q.add(cur.right);
              }
          }

• liuyubobobo 回复 提问者 qq_萌新_4 #2

  你的这个代码就是拿 queue 当 stack 用啊。add 和 remove 是在同一端操作的。

• 提问者 qq_萌新_4 回复 liuyubobobo #3

  嗷嗷 懂了