使用Java和递归的二级树遍历级别顺序遍历

我在使用递归时遇到二叉树的级别顺序遍历问题。 我输入以下值：50,60,70,30,20,10这是我正在使用的代码：

public void levelOrder(Node localRoot){ if(localRoot != null){ if(localRoot.leftChild != null && localRoot.rightChild != null){ System.out.print(localRoot.iData + " "); System.out.print(localRoot.leftChild.iData + " "); System.out.print(localRoot.rightChild.iData + " "); levelOrder(localRoot.leftChild); levelOrder(localRoot.rightChild); } else if(localRoot.rightChild == null && localRoot.leftChild == null){ ; } else if(localRoot.rightChild == null){ System.out.print(localRoot.leftChild.iData + " "); //levelOrder(localRoot.leftChild); } else{ System.out.print(localRoot.rightChild.iData + " "); //levelOrder(localRoot.rightChild); } } } 

不使用堆栈就可以递归吗？ 因为目前这个function一直带我到左边然后它正确。 我可以做些什么不同的事情？

我输出的代码是：50,30,60,20,70，它不打印10。

Answer 1

有趣的是，这是一个相当普遍的问题（谷歌“递归面包首次遍历”，并有几个类似答案的stackoverflow链接）

到目前为止，最好的就是这里

递归执行广度优先搜索

并且我同意顶部答案的作者，将迭代算法（广度优先遍历）转换为递归解决方案确实没有意义。 如上所述，它易于将迭代转换为尾递归，但到底是什么？ 而你仍然需要一个队列。

Answer 2

public void level（）{

  printLevel(root); 

}

 public void printLevel(Node current) { if(current != null){ if(current.leftChild != null && current.rightChild != null){ System.out.print(current.iData + " "); System.out.print(current.leftChild.iData + " "); System.out.print(current.rightChild.iData + " "); printLevel(current.leftChild); printLevel(current.rightChild); } else if(current.rightChild == null && current.leftChild == null){ ; } else if(current.rightChild == null){ System.out.print(current.leftChild.iData + " "); //levelOrder(current.leftChild); } else{ System.out.print(current.rightChild.iData + " "); //levelOrder(current.rightChild); } } } 

Answer 3

你可以使用队列来做到这一点：

 private Queue getLevelOrderKeys(Node root){ if (root == null) { return null; } Queue keyQueue = new ArrayDeque(); //return value. Queue with the level order keys Queue nodeQueue = new ArrayDeque(); nodeQueue.add(root); //while there is at least one discovered node while(!nodeQueue.isEmpty()) { Node current = nodeQueue.poll(); keyQueue.add(current.key); if (current.left != null){ nodeQueue.add(current.left); } if (current.right != null){ nodeQueue.add(current.right); } } return keyQueue; }