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

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

Example 1:

Input: root = [3, 9, 7, 20, 6, 5, 5, 7]

Output: [[15,7], [9,20], [3]]

Example 2:

Input: root = [1]

Output: [[1]]

Example 3:

Input: root = []

Output: []

Constraints:

The number of nodes in the tree is in the range [0, 2000].

-1000 val); if (t-> left) q.push (t-> left); if (t-> right) q.push (t-> right);} res.insert (res.begin (), oneLevel);} return res;}}

Let's take a look at the recursive solution. Because of the recursive nature, we will always give priority to the depth of the left child node, so it is bound to cross different layers, so when you want to add a node, you must know the current depth, so use a variable level to mark the current depth, and initialize it with 0, indicating the depth of the root node. Because what needs to be returned is a two-dimensional array res, at the beginning, because we do not know the depth of the binary tree and how many layers there are, it is impossible to apply for the size of the two-dimensional array, so it can only be increased continuously in the process of traversal. So when is it time to apply for a new layer? when level is equal to the size of a two-dimensional array, why is it equal to it? doesn't it mean to exceed the current depth? this is because level starts from 0, just like an array An of length n. You will make mistakes when you visit A [n]. When level equals the length of the array, you need to apply for a new layer, create a new empty layer, and continue to add numbers to it. See the code as follows:

Solution 2:

Class Solution {public: vector levelOrderBottom (TreeNode* root) {vector res; levelorder (root, 0, res); return vector (res.rbegin (), res.rend ());} 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);}}. These are all the contents of the article "C++ binary Tree sequence traversal example Analysis". 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.