下面是一个java $ C $下广度优先的行程：

Here is a java code for breadth-first travel:

void breadthFirstNonRecursive(){
    Queue<Node> queue = new java.util.LinkedList<Node>();
    queue.offer(root);
    while(!queue.isEmpty()){
        Node node = queue.poll();
        visit(node);
        if (node.left != null)
            queue.offer(node.left);
        if (node.right != null)
            queue.offer(node.right);
    }
}

是否可以写一个递归函数做？

Is it possible to write a recursive function to do the same?

起初，我认为这将是容易的，所以我来到了这一点：

At first, I thought this would be easy, so I came out with this:

void breadthFirstRecursive(){
    Queue<Node> q = new LinkedList<Node>();
    breadthFirst(root, q);
}

void breadthFirst(Node node, Queue<Node> q){
    if (node == null) return;
    q.offer(node);
    Node n = q.poll();
    visit(n);
    if (n.left != null)
        breadthFirst(n.left, q);
    if (n.right != null)
        breadthFirst(n.right, q);   
}

后来我发现这是行不通的。它实际上是做同样的事情，这样的：

Then I found it doesn't work. It is actually does the same thing as this:

void preOrder(Node node) {
    if (node == null) return;
    visit(node);
    preOrder(node.left);
    preOrder(node.right);
}

有没有人想过这之前？

Has any one thought about this before?

推荐答案

我无法想象的为什么的你会想，当你有一个完美的迭代求解，但在这里，你去; ）

I can't imagine why you'd want to, when you have a perfectly good iterative solution, but here you go ;)

void breadth_first(Node root):
  Queue q;
  q.push(root);
  breadth_first_recursive(q)

void breadth_first_recursive(Queue q):
  if q.empty() return;

  Node n = q.pop()
  print "Node: ", n
  if (n.left) q.push(n.left)
  if (n.right) q.push(n.right)
  breadth_first_recursive(q)

我要补充一点，如果你真的想遍历树的节点递归，那么你可以做一个DFS与水平参数，输出节点只在水平，然后递归了。但是，这只是疯狂的谈话，因为你会重温节点wayyyyy太多次了...只是接受BFS是一个迭代算法。 ：）

I should add that if you really want to traverse the nodes of the tree recursively, then you could do a DFS with a level parameter, and output nodes only at level, then recurse up. But that's just crazy talk, because you'd revisit nodes wayyyyy too many times... Just accept that BFS is an iterative algorithm. :)