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

Today, the editor will share with you the relevant knowledge points of C++ 's method of realizing binary tree sequence traversal. 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.

Binary tree sequence traversal

Given a binary tree, return the level order traversal of its nodes "values. (ie, from left to right, level by level).

For example:

Given binary tree {3,9,20,#,#,15,7}

three

/

9 20

/

15 7

Return its level order traversal as:

[

[3],

[9,20]

[15,7]

]

Sequence traversal binary tree is a typical breadth-first search BFS application, but what is a little more complicated here is that to separate the numbers of each layer and store them in a two-dimensional vector, the idea is basically the same. Set up a queue, and then first put the root node into it, then find the left and right child nodes of the root node, then remove the root node, and the elements in the queue are all the nodes in the next layer. Use a for loop to traverse them, then store them in an one-dimensional vector, and then store the one-dimensional vector in a two-dimensional vector, and so on, you can complete sequence traversal, see the code as follows:

Solution 1:

Class Solution {public: vector levelOrder (TreeNode* root) {if (! root) return {}; vector res; queue q {{root}}; 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);} res.push_back (oneLevel);} return res;}}

Let's take a look at the recursive writing. The core is that you need a two-dimensional array and a variable level. For more information on the role of level, please see the following code in another blog post, Binary Tree Level Order Traversal II:

Solution 2:

Class Solution {public: vector levelOrder (TreeNode* root) {vector res; levelorder (root, 0, res); return res;} void levelorder (TreeNode* node, int level, vector& res) {if (! node) return; if (res.size () = = level) res.push_back ({}); res[ level] .push _ back (node- > val) If (node- > left) levelorder (node- > left, level + 1, res); if (node- > right) levelorder (node- > right, level + 1, res);}}. That's all of the article entitled "how C++ implements binary tree sequence traversal". 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.