Shulou(Shulou.com)05/31 Report--

Today, the editor will share with you the relevant knowledge points about how C++ realizes the glyph sequence traversal of the binary tree. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article, let's take a look at it.

Zigzag sequence traversal of binary tree

For example:

Given binary tree [3,9,20,null,null,15,7]

three

/

9 20

/

15 7

Return its zigzag level order traversal as:

[

[3],

[20,9]

[15,7]

]

The zigzag sequence traversal of this binary tree is the deformation of the previous Binary Tree Level Order Traversal, except that one line traverses from left to right, and the next row traverses from right to left, crossing zigzag sequences. The most simple and direct method is to use sequence traversal, and use a variable cnt to count the current number of layers (starting from 0), and flip the node values of all odd layers, as shown in the code below:

Solution 1:

Class Solution {public: vector zigzagLevelOrder (TreeNode* root) {if (! root) return {}; vector res; queue q {{root}}; int cnt = 0; while (! q.empty ()) {vector oneLevel; for (int I = q.size (); I > 0;-I) {TreeNode* t = q.front () Q.pop (); oneLevel.push_back (t-> val); if (t-> left) q.push (t-> left); if (t-> right) q.push (t-> right);} if (cnt% 2 = = 1) reverse (oneLevel.begin (), oneLevel.end ()); res.push_back (oneLevel); + + cnt } return res;}}

We can optimize the above solution. Flipping the array is feasible, but it is time-consuming. If we can directly calculate the coordinates of each node value in the array, we can update it directly. Since the number of nodes in each layer is known, that is, the number of elements in the queue, the size of the array can be initialized directly. At this time, a variable leftToRight is used to mark the order, which is initially true. When this variable is true, the position of each array added is I itself. If the variable is false, it is added to the size-1-i position, which is directly equivalent to flipping the array. After traversing each layer, you need to flip the leftToRight variable and don't forget to add oneLevel to the result res, as shown in the following code:

Solution 2:

Class Solution {public: vector zigzagLevelOrder (TreeNode* root) {if (! root) return {}; vector res; queue q {{root}}; bool leftToRight = true; while (! q.empty ()) {int size = q.size (); vector oneLevel (size); for (int I = 0; I

Val; if (t-> left) q.push (t-> left); if (t-> right) q.push (t-> right);} leftToRight =! leftToRight; res.push_back (oneLevel);} return res;}}

We can also use recursive methods to solve the problem. In fact, preorder traversal is used here. The recursive function needs a variable level to record the current depth. Since level starts from 0, if the size of the result res is equal to level, you need to add a new empty set in the result res, which ensures that res [level] will not cross the bounds. After taking out the res [level], determine the parity of the levle. If it is an even number, add node- > val to the end of the oneLevel. If it is an odd number, add it to the beginning of the oneLevel. Then call the recursive function on the left and right child nodes of node respectively. In this case, you can input level+1, as shown in the code below:

Solution 3:

Class Solution {public: vector zigzagLevelOrder (TreeNode* root) {vector res; helper (root, 0, res); return res;} void helper (TreeNode* node, int level, vector& res) {if (! node) return; if (res.size () val); else oneLevel.insert (oneLevel.begin (), node- > val); helper (node- > left, level + 1, res) Helper (node- > right, level + 1, res);}}; these are all the contents of this article entitled "how C++ implements glyph traversal of binary trees". Thank you for reading! I believe you will gain a lot after reading this article. The editor will update different knowledge for you every day. If you want to learn more knowledge, please pay attention to the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.