如何从顶部开始逐级打印二叉树中的数据？

发布于 2024-07-26 08:11:36 字数 538 浏览 6 评论 0原文

这是

我想到的一个面试题的解决方案。它使用队列。

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

还有什么比这个不使用队列更好的解决方案吗？

原文

This is an interview question

I think of a solution.
It uses queue.

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

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

拒绝两难 2024-08-02 08:11:36

逐层遍历称为广度优先遍历。使用队列是执行此操作的正确方法。如果你想进行深度优先遍历，你可以使用堆栈。

不过，您的方式并不十分标准。
事情应该是这样的。

public Void BFS()    
{      
 Queue q = new Queue();
 q.Enqueue(root);//You don't need to write the root here, it will be written in the loop
 while (q.count > 0)
 {
    Node n = q.DeQueue();
    Console.Writeln(n.Value); //Only write the value when you dequeue it
    if (n.left !=null)
    {
        q.EnQueue(n.left);//enqueue the left child
    }
    if (n.right !=null)
    {
       q.EnQueue(n.right);//enque the right child
    }
 }
}

编辑

这是正在运行的算法。
假设您有一棵这样的树：

首先，根 (1) 将被排队。然后进入循环。
队列 (1) 中的第一项已出列并打印。
1 的子级从左到右入队，队列现在包含 {2, 3}
回到循环开始处
队列 (2) 中的第一项出列并打印
2 的子级从左到右入队，队列现在包含 {3, 4}
回到循环开始处
...

队列将在每个循环中包含这些值

1: {1}

2: {2, 3}

3: {3, 4}

4: {4, 5, 6}

5: {5, 6}

6: { 6}

7: {}//空，循环终止

输出：

Level by level traversal is known as Breadth-first traversal. Using a Queue is the proper way to do this. If you wanted to do a depth first traversal you would use a stack.

The way you have it is not quite standard though.
Here's how it should be.

public Void BFS()    
{      
 Queue q = new Queue();
 q.Enqueue(root);//You don't need to write the root here, it will be written in the loop
 while (q.count > 0)
 {
    Node n = q.DeQueue();
    Console.Writeln(n.Value); //Only write the value when you dequeue it
    if (n.left !=null)
    {
        q.EnQueue(n.left);//enqueue the left child
    }
    if (n.right !=null)
    {
       q.EnQueue(n.right);//enque the right child
    }
 }
}

Edit

Here's the algorithm at work.
Say you had a tree like so:

First, the root (1) would be enqueued. The loop is then entered.
first item in queue (1) is dequeued and printed.
1's children are enqueued from left to right, the queue now contains {2, 3}
back to start of loop
first item in queue (2) is dequeued and printed
2's children are enqueued form left to right, the queue now contains {3, 4}
back to start of loop
...

The queue will contain these values over each loop

1: {1}

2: {2, 3}

3: {3, 4}

4: {4, 5, 6}

5: {5, 6}

6: {6}

7: {}//empty, loop terminates

Output:

回复收藏 0 原文

旧梦荧光笔 2024-08-02 08:11:36

由于问题需要逐级打印树，因此应该有一种方法来确定何时在控制台上打印换行符。这是我的代码，它尝试通过将 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;
}

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,

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

回复收藏 0 原文

长伴 2024-08-02 08:11:36

让我们看看一些 Scala 解决方案。首先，我将定义一个非常基本的二叉树：

case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]])

我们将使用以下树：

您可以像这样定义树：

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))
                       )
                  )
             )

我们将定义一个 widthFirst 函数，它将遍历树，将所需的函数应用于每个元素。有了这个，我们将定义一个打印函数并像这样使用它：

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 中并不常见，但在这里得到了很好的利用。

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

case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]])

We'll use the following tree:

You define the tree like this:

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))
                       )
                  )
             )

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:

def printTree(tree: Tree[Any]) = 
  breadthFirst(tree, (t: Tree[Any]) => println(t.value))

printTree(myTree)

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

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

Next, Scala solution, queue, no recursion:

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 =>
    }
}

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.

回复收藏 0 原文

难如初 2024-08-02 08:11:36

C++：

  struct node{
    string key;
    struct node *left, *right;
  };

  void printBFS(struct node *root){
    std::queue<struct node *> q;
    q.push(root);

    while(q.size() > 0){
      int levelNodes = q.size();
      while(levelNodes > 0){
        struct node *p = q.front(); 
        q.pop();
        cout << " " << p->key ;
        if(p->left != NULL) q.push(p->left);
        if(p->right != NULL) q.push(p->right);
        levelNodes--;
      }
      cout << endl;
    }
  }

输入：

平衡树创建自：

 string a[] = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n"};

输出：

 g 
 c k 
 a e i m 
 b d f h j l n

算法：

创建一个链表节点的 ArrayList。
使用队列进行层序遍历（广度优先搜索）。
为了获取每个级别的所有节点，在从队列中取出节点之前，将队列的大小存储在一个变量中，假设您将其称为 levelNodes。
现在，当 levelNodes > 0，取出节点并打印并将它们的子节点添加到队列中。
在这个 while 循环之后放置一个换行符。

PS：我知道OP说，不用排队。我的回答只是为了表明是否有人正在寻找使用队列的 C++ 解决方案。

C++:

  struct node{
    string key;
    struct node *left, *right;
  };

  void printBFS(struct node *root){
    std::queue<struct node *> q;
    q.push(root);

    while(q.size() > 0){
      int levelNodes = q.size();
      while(levelNodes > 0){
        struct node *p = q.front(); 
        q.pop();
        cout << " " << p->key ;
        if(p->left != NULL) q.push(p->left);
        if(p->right != NULL) q.push(p->right);
        levelNodes--;
      }
      cout << endl;
    }
  }

Input :

Balanced tree created from:

 string a[] = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n"};

Output:

 g 
 c k 
 a e i m 
 b d f h j l n

Algorithm:

Create an ArrayList of Linked List Nodes.
Do the level order traversal using queue(Breadth First Search).
For getting all the nodes at each level, before you take out a node from queue, store the size of the queue in a variable, say you call it as levelNodes.
Now while levelNodes > 0, take out the nodes and print it and add their children into the queue.
After this while loop put a line break.

P.S: I know the OP said, no queue. My answer is just to show if someone is looking for a C++ solution using queue.

回复收藏 0 原文

徒留西风 2024-08-02 08:11:36

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

}

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

}

回复收藏 0 原文

简单 2024-08-02 08:11:36

为了按级别打印输出，可以将级别信息与节点一起存储为元组以添加到队列中。然后，每当级别更改时，您都可以打印新行。下面是执行此操作的 Python 代码。

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))

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.

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))

回复收藏 0 原文

骄兵必败 2024-08-02 08:11:36

试试这个（完整代码）：

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<HisNode> nodes = Arrays.asList(root);
        printByLevels(nodes);

    }

    private static void printByLevels(List<HisNode> nodes)
    {
        if (nodes == null || (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;
    }
}

Try this one (Complete 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<HisNode> nodes = Arrays.asList(root);
        printByLevels(nodes);

    }

    private static void printByLevels(List<HisNode> nodes)
    {
        if (nodes == null || (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;
    }
}

回复收藏 0 原文

演多会厌 2024-08-02 08:11:36

我认为您期望的是打印每个级别的节点，用空格或逗号分隔，并且级别由新行分隔。这就是我编写算法的方式。我们知道，当我们对图或树进行广度优先搜索并将节点插入队列时，队列中出现的所有节点将要么与前一个节点处于同一级别，要么处于父级别的新级别+ 1，没有别的。

因此，当您处于某个级别时，请继续打印节点值，一旦您发现该节点的级别增加了 1，则在开始打印该级别的所有节点之前插入一个新行。

这是我的代码，它不使用太多内存，所有内容只需要队列。

假设树从根开始。

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

最后，您所需要的只是用于所有处理的队列。

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.

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

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

回复收藏 0 原文

渡你暖光 2024-08-02 08:11:36

我调整了答案，以便它显示空节点并按高度打印它。
对于测试红黑树的平衡性来说实际上相当不错。可以
还将颜色添加到打印线中以检查黑色高度。

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

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.

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

回复收藏 0 原文

心是晴朗的。 2024-08-02 08:11:36

当然你不需要使用队列。这是在Python中。

# 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 > 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)

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

# 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 > 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)

回复收藏 0 原文

︶￣淡然 2024-08-02 08:11:36

尝试使用下面的代码。

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

Try with below code.

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

回复收藏 0 原文

暖树树初阳… 2024-08-02 08:11:36

这是我的答案。

//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)}
        }

    }

这里的children是一个数组，存储节点的子节点。

here is my answer.

//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)}
        }

    }

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

回复收藏 0 原文

~没有更多了~