这是一个面试问题
我想出了一个解决方案。它使用队列。
public Void BFS()
{
Queue q = new Queue();
q.Enqueue(root);
Console.WriteLine(root.Value);
while (q.count > 0)
{
Node n = q.DeQueue();
if (n.left !=null)
{
Console.Writeln(n.left);
q.EnQueue(n.left);
}
if (n.right !=null)
{
Console.Writeln(n.right);
q.EnQueue(n.right);
}
}
}
还有比这更好的解决方案吗?它不使用队列。
发布于 2012-05-05 11:53:14
由于问题需要逐层打印树,因此应该有一种方法来确定何时在控制台上打印换行符。下面是我的代码,它试图通过将NewLine节点附加到队列来执行相同的操作,
void PrintByLevel(Node *root)
{
Queue q;
Node *newline = new Node("\n");
Node *v;
q->enque(root);
q->enque(newline);
while(!q->empty()) {
v = q->deque();
if(v == newline) {
printf("\n");
if(!q->empty())
q->enque(newline);
}
else {
printf("%s", v->val);
if(v->Left)
q-enque(v->left);
if(v->right)
q->enque(v->right);
}
}
delete newline;
}
发布于 2009-07-09 23:03:11
让我们来看看一些Scala解决方案。首先,我将定义一个非常基本的二叉树:
case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]])
我们将使用以下树:
1
/ \
2 3
/ / \
4 5 6
您可以这样定义树:
val myTree = Tree(1,
Some(Tree(2,
Some(Tree(4, None, None)),
None
)
),
Some(Tree(3,
Some(Tree(5, None, None)),
Some(Tree(6, None, None))
)
)
)
我们将定义一个breadthFirst函数,该函数将遍历树,将所需的函数应用于每个元素。在这里,我们将定义一个print函数,并像这样使用它:
def printTree(tree: Tree[Any]) =
breadthFirst(tree, (t: Tree[Any]) => println(t.value))
printTree(myTree)
现在,Scala解决方案,递归,列表,但没有队列:
def breadthFirst[T](t: Tree[T], f: Tree[T] => Unit): Unit = {
def traverse(trees: List[Tree[T]]): Unit = trees match {
case Nil => // do nothing
case _ =>
val children = for{tree <- trees
Some(child) <- List(tree.left, tree.right)}
yield child
trees map f
traverse(children)
}
traverse(List(t))
}
接下来,Scala解决方案,队列,无递归:
def breadthFirst[T](t: Tree[T], f: Tree[T] => Unit): Unit = {
import scala.collection.mutable.Queue
val queue = new Queue[Option[Tree[T]]]
import queue._
enqueue(Some(t))
while(!isEmpty)
dequeue match {
case Some(tree) =>
f(tree)
enqueue(tree.left)
enqueue(tree.right)
case None =>
}
}
这种递归解决方案功能齐全,但我有一种不安的感觉,那就是它还可以进一步简化。
队列版本不起作用,但它非常有效。关于导入对象的部分在Scala中并不常见,但在这里可以很好地使用。
发布于 2014-11-12 15:53:37
public class LevelOrderTraversalQueue {
Queue<Nodes> qe = new LinkedList<Nodes>();
public void printLevelOrder(Nodes root)
{
if(root == null) return;
qe.add(root);
int count = qe.size();
while(count!=0)
{
System.out.print(qe.peek().getValue());
System.out.print(" ");
if(qe.peek().getLeft()!=null) qe.add(qe.peek().getLeft());
if(qe.peek().getRight()!=null) qe.add(qe.peek().getRight());
qe.remove(); count = count -1;
if(count == 0 )
{
System.out.println(" ");
count = qe.size();
}
}
}
}
https://stackoverflow.com/questions/1104644
复制相似问题