blocks|key|1508208|text|让我们来看看一些Scala解决方案。首先，我将定义一个非常基本的二叉树：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1508209|case+class+Tree[%2BT](value:+T,+left:+Option[Tree[T]],+right:+Option[Tree[T]])|code-block|syntax|javascript|1508210|我们将使用以下树：|1508211|++++1
+++/+\
++2+++3
+/+++/+\
4+++5+++6|1508212|您可以这样定义树：|1508213|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))
+++++++++++++++++++++++)
++++++++++++++++++)
+++++++++++++)|1508214|我们将定义一个breadthFirst函数，该函数将遍历树，将所需的函数应用于每个元素。在这里，我们将定义一个print函数，并像这样使用它：|1508215|def+printTree(tree:+Tree[Any])+=+
++breadthFirst(tree,+(t:+Tree[Any])+=>+println(t.value))

printTree(myTree)|1508216|现在，Scala解决方案，递归，列表，但没有队列：|1508217|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))
}|1508218|接下来，Scala解决方案，队列，无递归：|1508219|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+=>
++++}
}|1508220|这种递归解决方案功能齐全，但我有一种不安的感觉，那就是它还可以进一步简化。|1508221|队列版本不起作用，但它非常有效。关于导入对象的部分在Scala中并不常见，但在这里可以很好地使用。|1508222|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|16|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|17|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|18|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|19|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|1A|8|@]|9|@]|A|$]]|$1|M|3|N|5|D|7|1B|8|@]|9|@]|A|$E|F]]|$1|O|3|P|5|6|7|1C|8|@]|9|@]|A|$]]|$1|Q|3|R|5|D|7|1D|8|@]|9|@]|A|$E|F]]|$1|S|3|T|5|6|7|1E|8|@]|9|@]|A|$]]|$1|U|3|V|5|D|7|1F|8|@]|9|@]|A|$E|F]]|$1|W|3|X|5|6|7|1G|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|D|7|1H|8|@]|9|@]|A|$E|F]]|$1|10|3|11|5|6|7|1I|8|@]|9|@]|A|$]]|$1|12|3|13|5|6|7|1J|8|@]|9|@]|A|$]]|$1|14|3|-4|5|6|7|1K|8|@]|9|@]|A|$]]]|15|$]]

Let's see some Scala solutions. First, I'll define a very basic binary tree:

<pre><code>case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]])
</code></pre>

We'll use the following tree:

<pre><code> 1
 / \
 2 3
 / / \
4 5 6
</code></pre>

You define the tree like this:

<pre><code>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))
 )
 )
 )
</code></pre>

We'll define a breadthFirst function which will traverse the tree applying the desired function to each element. With this, we'll define a print function and use it like this:

<pre><code>def printTree(tree: Tree[Any]) = 
 breadthFirst(tree, (t: Tree[Any]) =&gt; println(t.value))

printTree(myTree)
</code></pre>

Now, Scala solution, recursive, lists but no queues:

<pre><code>def breadthFirst[T](t: Tree[T], f: Tree[T] =&gt; Unit): Unit = {
 def traverse(trees: List[Tree[T]]): Unit = trees match {
 case Nil =&gt; // do nothing
 case _ =&gt;
 val children = for{tree &lt;- trees
 Some(child) &lt;- List(tree.left, tree.right)} 
 yield child
 trees map f
 traverse(children)
 }

 traverse(List(t))
}
</code></pre>

Next, Scala solution, queue, no recursion:

<pre><code>def breadthFirst[T](t: Tree[T], f: Tree[T] =&gt; 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) =&gt; 
 f(tree)
 enqueue(tree.left)
 enqueue(tree.right)
 case None =&gt;
 }
}
</code></pre>

That recursive solution is fully functional, though I have an uneasy feeling that it can be further simplified.

The queue version is not functional, but it is highly effective. The bit about importing an object is unusual in Scala, but put to good use here.

blocks|key|1508299|text|为了按级别打印输出，您可以将级别信息与节点一起存储为元组，以添加到队列中。然后，每当级别发生变化时，您都可以打印新行。下面是一段Python代码来实现这一点。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1508300|from+collections+import+deque
class+BTreeNode:
++++def+__init__(self,+data,+left=None,+right=None):
++++++++self.data+=+data
++++++++self.left+=+left
++++++++self.right+=+right

++++def+printLevel(self):
++++++++"""+Breadth-first+traversal,+print+out+the+data+by+level+"""
++++++++level+=+0
++++++++lastPrintedLevel+=+0
++++++++visit+=+deque([])
++++++++visit.append((self,+level))
++++++++while+len(visit)+!=+0:
++++++++++++item+=+visit.popleft()
++++++++++++if+item[1]+!=+lastPrintedLevel:++#New+line+for+a+new+level
++++++++++++++++lastPrintedLevel+%2B=1
++++++++++++++++print
++++++++++++print+item[0].data,
++++++++++++if+item[0].left+!=+None:
++++++++++++++++visit.append((item[0].left,+item[1]+%2B+1))
++++++++++++if+item[0].right+!=+None:+
++++++++++++++++visit.append((item[0].right,+item[1]+%2B+1))|code-block|syntax|javascript|1508301|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

In order to print out by level, you can store the level information with the node as a tuple to add to the queue. Then you can print a new line whenever the level is changed. Here is a Python code to do so.

<pre><code>from collections import deque
class BTreeNode:
 def __init__(self, data, left=None, right=None):
 self.data = data
 self.left = left
 self.right = right

 def printLevel(self):
 """ Breadth-first traversal, print out the data by level """
 level = 0
 lastPrintedLevel = 0
 visit = deque([])
 visit.append((self, level))
 while len(visit) != 0:
 item = visit.popleft()
 if item[1] != lastPrintedLevel: #New line for a new level
 lastPrintedLevel +=1
 print
 print item[0].data,
 if item[0].left != None:
 visit.append((item[0].left, item[1] + 1))
 if item[0].right != None: 
 visit.append((item[0].right, item[1] + 1))
</code></pre>

blocks|key|1293766|text|由于问题需要逐层打印树，因此应该有一种方法来确定何时在控制台上打印换行符。下面是我的代码，它试图通过将NewLine节点附加到队列来执行相同的操作，|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1293767|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("%25s",+v->val);
+++++++++if(v->Left)
++++++++++++q-enque(v->left);
+++++++++if(v->right)
++++++++++++q->enque(v->right);
++++++}
+++}
+++delete+newline;
}|code-block|syntax|javascript|1293768|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Since the question requires printing the tree level by level, there should be a way to determine when to print the new line character on the console. Here's my code which tries to do the same by appending NewLine node to the queue,

<pre><code>void PrintByLevel(Node *root)
{
 Queue q;
 Node *newline = new Node("\n");
 Node *v;
 q-&gt;enque(root);
 q-&gt;enque(newline);

 while(!q-&gt;empty()) {
 v = q-&gt;deque();
 if(v == newline) {
 printf("\n");
 if(!q-&gt;empty())
 q-&gt;enque(newline);
 }
 else {
 printf("%s", v-&gt;val);
 if(v-&gt;Left)
 q-enque(v-&gt;left);
 if(v-&gt;right)
 q-&gt;enque(v-&gt;right);
 }
 }
 delete newline;
}
</code></pre>

blocks|key|1508446|text|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();
++++++++++++}
++++++++}+++++++++++
++++}

}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1508447|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>public class LevelOrderTraversalQueue { 

 Queue&lt;Nodes&gt; qe = new LinkedList&lt;Nodes&gt;();

 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();
 }
 } 
 }

}
</code></pre>

blocks|key|1508478|text|我调整了答案，使其显示空节点并按高度打印。对于测试一棵红黑树的平衡性来说，实际上是相当不错的。能|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1508479|另外，将颜色添加到打印线中以检查黑色高度。|1508480|++++Queue<node>+q+=+new+Queue<node>();
++++int[]+arr+=+new+int[]{1,2,4,8,16,32,64,128,256};
++++int+i+=0;
++++int+b+=+0;
++++int+keeper+=+0;
++++public+void+BFS()
++++{


++++++++q.Enqueue(root);
++++++++while+(q.Count+>+0)
++++++++{

++++++++++++node+n+=+q.Dequeue();

++++++++++++if+(i+==+arr[b])
++++++++++++{

++++++++++++++++System.Diagnostics.Debug.Write("\r\n"%2B"("%2Bn.id%2B")");+
++++++++++++++++b%2B%2B;
++++++++++++++++i+=0+;
++++++++++++}
++++++++++++else+{

++++++++++++++++System.Diagnostics.Debug.Write("("+%2B+n.id+%2B+")");+

++++++++++++}
++++++++++++i%2B%2B;+


++++++++++++if+(n.id+!=+-1)
++++++++++++{



++++++++++++++++if+(n.left+!=+null)
++++++++++++++++{

++++++++++++++++++++q.Enqueue(n.left);
++++++++++++++++}
++++++++++++++++else
++++++++++++++++{
++++++++++++++++++++node+c+=+new+node();
++++++++++++++++++++c.id+=+-1;
++++++++++++++++++++c.color+=+'b';
++++++++++++++++++++q.Enqueue(c);
++++++++++++++++}

++++++++++++++++if+(n.right+!=+null)
++++++++++++++++{

++++++++++++++++++++q.Enqueue(n.right);
++++++++++++++++}
++++++++++++++++else
++++++++++++++++{
++++++++++++++++++++node+c+=+new+node();
++++++++++++++++++++c.id+=+-1;
++++++++++++++++++++c.color+=+'b';
++++++++++++++++++++q.Enqueue(c);

++++++++++++++++}
++++++++++++}

++++++++}
++++++++i+=+0;
++++++++b+=+0;
++++++++System.Diagnostics.Debug.Write("\r\n");
++++}|code-block|syntax|javascript|1508481|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

I tweaked the answer so that it shows the null nodes and prints it by height.
 Was actually fairly decent for testing the balance of a red black tree. can 
 also add the color into the print line to check black height. 

<pre><code> Queue&lt;node&gt; q = new Queue&lt;node&gt;();
 int[] arr = new int[]{1,2,4,8,16,32,64,128,256};
 int i =0;
 int b = 0;
 int keeper = 0;
 public void BFS()
 {


 q.Enqueue(root);
 while (q.Count &gt; 0)
 {

 node n = q.Dequeue();

 if (i == arr[b])
 {

 System.Diagnostics.Debug.Write("\r\n"+"("+n.id+")"); 
 b++;
 i =0 ;
 }
 else {

 System.Diagnostics.Debug.Write("(" + n.id + ")"); 

 }
 i++; 


 if (n.id != -1)
 {



 if (n.left != null)
 {

 q.Enqueue(n.left);
 }
 else
 {
 node c = new node();
 c.id = -1;
 c.color = 'b';
 q.Enqueue(c);
 }

 if (n.right != null)
 {

 q.Enqueue(n.right);
 }
 else
 {
 node c = new node();
 c.id = -1;
 c.color = 'b';
 q.Enqueue(c);

 }
 }

 }
 i = 0;
 b = 0;
 System.Diagnostics.Debug.Write("\r\n");
 }
</code></pre>

blocks|key|1293857|text|试试这个(完整代码)：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1293858|class+HisTree
{
++++public+static+class+HisNode
++++{
++++++++private+int+data;
++++++++private+HisNode+left;
++++++++private+HisNode+right;

++++++++public+HisNode()+{}
++++++++public+HisNode(int+_data+,+HisNode+_left+,+HisNode+_right)
++++++++{
++++++++++++data+=+_data;
++++++++++++right+=+_right;
++++++++++++left+=+_left;
++++++++}
++++++++public+HisNode(int+_data)
++++++++{
++++++++++++data+=+_data;
++++++++}
++++}

++++public+static+int+height(HisNode+root)
++++{
++++++++if+(root+==+null)
++++++++{
++++++++++++return+0;
++++++++}

++++++++else
++++++++{
++++++++++++return+1+%2B+Math.max(height(root.left),+height(root.right));
++++++++}
++++}


++++public+static+void+main(String[]+args)
++++{
//++++++++++1
//+++++++++/++\+
//++++++++/++++\
//+++++++2++++++3
//++++++/+\++++/+\++
//+++++4++++5+6+++7
//++++/
//+++21

++++++++HisNode+root1+=+new+HisNode(3+,+new+HisNode(6)+,+new+HisNode(7));
++++++++HisNode+root3+=+new+HisNode(4+,+new+HisNode(21)+,+null);
++++++++HisNode+root2+=+new+HisNode(2+,+root3+,+new+HisNode(5));
++++++++HisNode+root+=+new+HisNode(1+,+root2+,+root1);
++++++++printByLevels(root);
++++}


++++private+static+void+printByLevels(HisNode+root)+{

++++++++List<HisNode>+nodes+=+Arrays.asList(root);
++++++++printByLevels(nodes);

++++}

++++private+static+void+printByLevels(List<HisNode>+nodes)
++++{
++++++++if+(nodes+==+null+%7C%7C+(nodes+!=+null+&&+nodes.size()+<=+0))
++++++++{
++++++++++++return;
++++++++}
++++++++List+<HisNode>+nodeList+=+new+LinkedList<HisNode>();
++++++++for+(HisNode+node+:+nodes)
++++++++{
++++++++++++if+(node+!=+null)
++++++++++++{
++++++++++++++++System.out.print(node.data);
++++++++++++++++System.out.print("+,+");
++++++++++++++++nodeList.add(node.left);
++++++++++++++++nodeList.add(node.right);
++++++++++++}
++++++++}
++++++++System.out.println();
++++++++if+(nodeList+!=+null+&&+!CheckIfNull(nodeList))
++++++++{
++++++++++++printByLevels(nodeList);++++
++++++++}
++++++++else
++++++++{
++++++++++++return;
++++++++}

++++}


++++private+static+boolean+CheckIfNull(List<HisNode>+list)
++++{
++++++++for(HisNode+elem+:+list)
++++++++{
++++++++++++if+(elem+!=+null)
++++++++++++{
++++++++++++++++return+false;
++++++++++++}
++++++++}
++++++++return+true;
++++}
}|code-block|syntax|javascript|1293859|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Try this one (Complete code) : 

<pre><code>class HisTree
{
 public static class HisNode
 {
 private int data;
 private HisNode left;
 private HisNode right;

 public HisNode() {}
 public HisNode(int _data , HisNode _left , HisNode _right)
 {
 data = _data;
 right = _right;
 left = _left;
 }
 public HisNode(int _data)
 {
 data = _data;
 }
 }

 public static int height(HisNode root)
 {
 if (root == null)
 {
 return 0;
 }

 else
 {
 return 1 + Math.max(height(root.left), height(root.right));
 }
 }


 public static void main(String[] args)
 {
// 1
// / \ 
// / \
// 2 3
// / \ / \ 
// 4 5 6 7
// /
// 21

 HisNode root1 = new HisNode(3 , new HisNode(6) , new HisNode(7));
 HisNode root3 = new HisNode(4 , new HisNode(21) , null);
 HisNode root2 = new HisNode(2 , root3 , new HisNode(5));
 HisNode root = new HisNode(1 , root2 , root1);
 printByLevels(root);
 }


 private static void printByLevels(HisNode root) {

 List&lt;HisNode&gt; nodes = Arrays.asList(root);
 printByLevels(nodes);

 }

 private static void printByLevels(List&lt;HisNode&gt; nodes)
 {
 if (nodes == null || (nodes != null &amp;&amp; nodes.size() &lt;= 0))
 {
 return;
 }
 List &lt;HisNode&gt; nodeList = new LinkedList&lt;HisNode&gt;();
 for (HisNode node : nodes)
 {
 if (node != null)
 {
 System.out.print(node.data);
 System.out.print(" , ");
 nodeList.add(node.left);
 nodeList.add(node.right);
 }
 }
 System.out.println();
 if (nodeList != null &amp;&amp; !CheckIfNull(nodeList))
 {
 printByLevels(nodeList); 
 }
 else
 {
 return;
 }

 }


 private static boolean CheckIfNull(List&lt;HisNode&gt; list)
 {
 for(HisNode elem : list)
 {
 if (elem != null)
 {
 return false;
 }
 }
 return true;
 }
}
</code></pre>

blocks|key|1508579|text|当然，您不需要使用队列。这是用python编写的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1508580|#+Function+to++print+level+order+traversal+of+tree
def+printLevelOrder(root):
++++h+=+height(root)
++++for+i+in+range(1,+h%2B1):
++++++++printGivenLevel(root,+i)


#+Print+nodes+at+a+given+level
def+printGivenLevel(root+,+level):
++++if+root+is+None:
++++++++return
++++if+level+==+1:
++++++++print+"%25d"+%25(root.data),
++++elif+level+>+1+:
++++++++printGivenLevel(root.left+,+level-1)
++++++++printGivenLevel(root.right+,+level-1)


"""+Compute+the+height+of+a+tree--the+number+of+nodes
++++along+the+longest+path+from+the+root+node+down+to
++++the+farthest+leaf+node
"""
def+height(node):
++++if+node+is+None:
++++++++return+0
++++else+:
++++++++#+Compute+the+height+of+each+subtree+
++++++++lheight+=+height(node.left)
++++++++rheight+=+height(node.right)
++++++++return+max(lheight,+reight)|code-block|syntax|javascript|1508581|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Of course you don't need to use queue. This is in python.

<pre><code># Function to print level order traversal of tree
def printLevelOrder(root):
 h = height(root)
 for i in range(1, h+1):
 printGivenLevel(root, i)


# Print nodes at a given level
def printGivenLevel(root , level):
 if root is None:
 return
 if level == 1:
 print "%d" %(root.data),
 elif level &gt; 1 :
 printGivenLevel(root.left , level-1)
 printGivenLevel(root.right , level-1)


""" Compute the height of a tree--the number of nodes
 along the longest path from the root node down to
 the farthest leaf node
"""
def height(node):
 if node is None:
 return 0
 else :
 # Compute the height of each subtree 
 lheight = height(node.left)
 rheight = height(node.right)
 return max(lheight, reight)
</code></pre>

blocks|key|1293991|text|我认为您所期望的是打印每个级别的节点，这些节点由空格或逗号分隔，级别由新行分隔。这就是我编写算法的方式。我们知道，当我们在图或树上进行广度优先搜索并将节点插入队列中时，队列中的所有节点都将处于与前一个节点相同的级别，或者是父级%2B1而不是其他级别的新级别。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1293992|因此，当您处于某个级别时，继续打印节点值，一旦发现节点级别增加了1，则在开始打印该级别的所有节点之前插入新行。|1293993|这是我的代码，它不占用太多内存，只需要队列就行了。|1293994|假设树是从根开始的。|1293995|queue+=+[(root,+0)]++#+Store+the+node+along+with+its+level.+
prev+=+0
while+queue:
++node,+level+=+queue.pop(0)
++if+level+==+prev:
++++print(node.val,+end+=+"")
++else:
++++print()
++++print(node.val,+end+=+"")
++if+node.left:
++++queue.append((node.left,+level+%2B+1))
++if+node.right:
++++queue.append((node.right,+level+%2B+1))
++prev+=+level|code-block|syntax|javascript|1293996|最后，您所需要的就是所有处理的队列。|1293997|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|S|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|T|8|@]|9|@]|A|$]]|$1|H|3|I|5|J|7|U|8|@]|9|@]|A|$K|L]]|$1|M|3|N|5|6|7|V|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

I think what you expecting is to print the nodes at each level either separated by a space or a comma and the levels be separated by a new line. This is how I would code up the algorithm. We know that when we do a breadth-first search on a graph or tree and insert the nodes in a queue, all nodes in the queue coming out will be either at the same level as the one previous or a new level which is parent level + 1 and nothing else. 

So when you are at a level keep printing out the node values and as soon as you find that the level of the node increases by 1, then you insert a new line before starting to print all the nodes at that level. 

This is my code which does not use much memory and only the queue is needed for everything. 

Assuming the tree starts from the root. 

<pre><code>queue = [(root, 0)] # Store the node along with its level. 
prev = 0
while queue:
 node, level = queue.pop(0)
 if level == prev:
 print(node.val, end = "")
 else:
 print()
 print(node.val, end = "")
 if node.left:
 queue.append((node.left, level + 1))
 if node.right:
 queue.append((node.right, level + 1))
 prev = level
</code></pre>

At the end all you need is the queue for all the processing.

blocks|key|1508689|text|尝试使用下面的代码。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1508690|public+void+printLevelOrder(TreeNode+root)+{
++++if+(root+==+null)+{
++++++++return;
++++}
++++Queue<TreeNode>+nodesToVisit+=+new+LinkedList<>();
++++nodesToVisit.add(root);

++++int+count+=+nodesToVisit.size();

++++while+(count+!=+0)+{
++++++++TreeNode+node+=+nodesToVisit.remove();

++++++++System.out.print("+"+%2B+node.data);

++++++++if+(node.left+!=+null)+{
++++++++++++nodesToVisit.add(node.left);
++++++++}

++++++++if+(node.right+!=+null)+{
++++++++++++nodesToVisit.add(node.right);
++++++++}

++++++++count--;

++++++++if+(count+==+0)+{
++++++++++++System.out.println("");
++++++++++++count+=+nodesToVisit.size();
++++++++}
++++}
}|code-block|syntax|javascript|1508691|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Try with below code.

<pre><code>public void printLevelOrder(TreeNode root) {
 if (root == null) {
 return;
 }
 Queue&lt;TreeNode&gt; nodesToVisit = new LinkedList&lt;&gt;();
 nodesToVisit.add(root);

 int count = nodesToVisit.size();

 while (count != 0) {
 TreeNode node = nodesToVisit.remove();

 System.out.print(" " + node.data);

 if (node.left != null) {
 nodesToVisit.add(node.left);
 }

 if (node.right != null) {
 nodesToVisit.add(node.right);
 }

 count--;

 if (count == 0) {
 System.out.println("");
 count = nodesToVisit.size();
 }
 }
}
</code></pre>

blocks|key|1508716|text|这是我的答案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1508717|//for+level+order+traversal
++++func+forEachLevelOrder(_+visit+:+(TreeNode)+->+Void)+{

++++++++visit(self)
++++++++var+queue+=+Queue<TreeNode>()
++++++++children.forEach+{
++++++++++++queue.Enqueue($0)
++++++++}
++++++++while+let+node+=+queue.Dequeue()+{
++++++++++++visit(node)
++++++++++++node.children.forEach+{+queue.Enqueue($0)}
++++++++}

++++}|code-block|syntax|javascript|1508718|子节点在这里是一个存储节点的子节点的数组。|1508719|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

here is my answer.

<pre><code>//for level order traversal
 func forEachLevelOrder(_ visit : (TreeNode) -&gt; Void) {

 visit(self)
 var queue = Queue&lt;TreeNode&gt;()
 children.forEach {
 queue.Enqueue($0)
 }
 while let node = queue.Dequeue() {
 visit(node)
 node.children.forEach { queue.Enqueue($0)}
 }

 }
</code></pre>

children is an array here that stores the children of a node.

This is an interview question

I think of a solution.
It uses queue.

<pre><code>public Void BFS() 
{ 
 Queue q = new Queue(); 
 q.Enqueue(root); 
 Console.WriteLine(root.Value); 

 while (q.count &gt; 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); 
 } 
 }
} 
</code></pre>

Can anything think of better solution than this, which doesn't use Queue?

How would you print out the data in a binary tree, level by level, starting at the top?

Python

这是一个面试问题我想出了一个解决方案。它使用队列。public Void BFS()    {      Queue q = new Queue();       q.Enqueue(root);       Console.WriteLine(root.Value);     while (q.count > 0) ...

问如何打印二叉树中的数据，从顶层开始逐层打印？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何打印二叉树中的数据，从顶层开始逐层打印？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何打印二叉树中的数据，从顶层开始逐层打印？
EN