Detailed explanation of binary Tree sequence traversal in Java

This article mainly explains "Detailed explanation of binary tree sequence traversal in Java". The explanation content in this article is simple and clear, easy to learn and understand. Please follow the idea of Xiaobian and go deep into it slowly to study and learn "Detailed explanation of binary tree sequence traversal in Java" together.

sequence traversal

Sequence traversal, also known by the name is layer traversal. A node has left and right nodes, and processing by layer means that the priority of the sibling node at the current layer is greater than the priority of the child node processing, so it is necessary to put the child node behind for processing, which is suitable for the queue data structure for storage.

For queues, first in, first out. From the root node push to the queue, then the queue first out of the order is the second layer left and right (assuming there are), the second layer of each node execution time according to the left and right order added to the queue, the third layer of nodes will be orderly placed at the end...... according to such rules can get a sequence traversal order.

The implementation code is also easy to understand:

public int[] levelOrder(TreeNode root) { int arr[]=new int[10000]; int index=0; Queuequeue=new ArrayDeque(); if(root!= null) queue.add(root); while (! queue.isEmpty()){ TreeNode node=queue.poll(); arr[index++]= node.val; if(node.left!= null) queue.add(node.left); if(node.right!= null) queue.add(node.right); } return Arrays.copyOf(arr,index); } Tiered storage

But in the specific written test he may ask you to store hierarchically, for example, the sequence traversal of the 102 binary tree of the force button requires returning a List type.

This kind of logic is one more layer than the above one, which is to put each layer of data into one piece. This is also very easy. The best thing to think of is two queues (containers), one layer at a time, traversing storage, and then alternating. However, the writing of two queues (containers) is often rejected by interviewers. Many interviewers ask you to think about how to implement it without two containers.

It is easy to enumerate the results without double queues. The important thing is to record the queue size(the number of nodes in the current layer) first, and then execute the enumeration of the number of times of size. The specific code is:

public List levelOrder(TreeNode root) { Listlist=new ArrayList(); if(root==null)return list; Queueq1=new ArrayDeque(); q1.add(root); while (! q1.isEmpty()) { int size=q1.size(); Listvalue=new ArrayList(); for(int i=0;i