On the sequence traversal of binary tree Ⅱ

Topic link ： Sequence traversal of binary tree Ⅱ

Title Description

Give you the root node of the binary tree root , Returns its node value Bottom up sequence traversal . （ That is, from the layer where the leaf node is to the layer where the root node is , Traversal layer by layer from left to right ）

Topic analysis

The topic here looks very difficult , If the binary tree is traversed from bottom to top , It seems hard to do . But you might as well change your mind , If you reverse the two-dimensional array formed by traversing the binary tree from top to bottom , Is it equivalent to bottom-up traversal . thus , The train of thought is very clear . The normal sequence traversal method of binary tree can refer to the previous blog , I won't go into that , Here, you only need to reverse the final result to pass , The code is as follows ：

Code implementation

vector<vector<int>> levelOrderBottom(TreeNode* root) 
{
    
	vector<vector<int>> ret;
	queue<TreeNode*> q;
	if (root)
	{
    
		q.push(root);
	}
	int levelsize = q.size();
	while (!q.empty())
	{
    
		vector<int> tmp;
		while (levelsize)
		{
    
			TreeNode* cur = q.front();
			q.pop();
			tmp.push_back(cur->val);
			if (cur->left)
			{
    
				q.push(cur->left);
			}
			if (cur->right)
			{
    
				q.push(cur->right);
			}
			levelsize--;
		}
		ret.push_back(tmp);
		levelsize = q.size();
	}
	reverse(ret.begin(), ret.end());
	return ret;
}