利用二叉树层序遍历输出每层数据

107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

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

3 / \ 9 20 / \ 15 7

return its bottom-up level order traversal as:

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

本题的思路也是层序遍历，同时通过控制队列大小来控制位于同一层，可以认为与求二叉树每层平均值思路一致。

代码如下：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> v1; vector<vector<int>> v; vector<int> v2; TreeNode *temp = root; queue<TreeNode *> q; if (temp == NULL) return v; q.push(temp); v2.push_back(temp->val); v1.push_back(v2); v2.clear(); while (!q.empty()) { int i = q.size(); for (int j = 0; j < i; j++) { TreeNode *top = q.front(); q.pop(); if (top->left != NULL) { q.push(top->left); v2.push_back(top->left->val); } if (top->right != NULL) { q.push(top->right); v2.push_back(top->right->val); } } if (!v2.empty()) v1.push_back(v2); v2.clear(); } while (!v1.empty()) { v.push_back(v1.back()); v1.pop_back(); } return v; } };