▶ 有关将一棵二叉树转化为二位表的题目，一模一样的套路出了四道题
▶ 第 102 题，简单的转化，[ 3, 9, 20, null, null, 15, 7 ] 转为 [ [ 15, 7 ] , [ 9, 20 ] , [ 3 ] ]
● 自己的代码，6 ms，先根序遍历，最快的解法算法与之相同
class Solution
{
public:
void visit(TreeNode* root, vector<vector<int>>& table, int level)
{
if (root == nullptr)
return;
if (table.size() <= level) // 首次到达该深度，建立新的一层
table.push_back(vector<int>());
visit(root->left, table, level + );
table[level].push_back(root->val);
visit(root->right, table, level + );
return;
}
vector<vector<int>> levelOrderBottom(TreeNode* root)
{
vector<vector<int>> output;
if (root == nullptr)
return output;
visit(root, output, );
return output;
}
};
▶ 第 103 题，要求奇数行顺序输出，偶数行倒序输出，在第 102 题的基础上加个函数 reverse() 就行
● 自己的代码，4 ms，基于第 102 题，最快的解法算法与之相同
class Solution
{
public:
void visit(TreeNode* root, vector<vector<int>>& table, int level)
{
if (root == nullptr)
return;
if (table.size() <= level) // 首次到达该深度，建立新的一层
table.push_back(vector<int>());
visit(root->left, table, level + );
table[level].push_back(root->val);
visit(root->right, table, level + );
return;
}
vector<vector<int>> levelOrderBottom(TreeNode* root)
{
vector<vector<int>> output;
if (root == nullptr)
return output;
visit(root, output, );
for (int i = ; i < output.size(); i += )
reverse(output[i].begin(), output[i].end());
return output;
}
};
▶ 第 107 题，要求倒序输出，还是在第 102 题 的基础上加个函数 reverse() 就行
● 自己的代码，5 ms，最快的解法算法与之相同，但是使用的数据结构是 list，新建一层用的是函数 resize()
class Solution
{
public:
void visit(TreeNode* root, vector<vector<int>>& table, int level)
{
if (root == nullptr)
return;
if (table.size() <= level) // 首次到达该深度，建立新的一层
table.push_back(vector<int>());
visit(root->left, table, level + );
table[level].push_back(root->val);
visit(root->right, table, level + );
return;
}
vector<vector<int>> levelOrderBottom(TreeNode* root)
{
vector<vector<int>> output;
if (root == nullptr)
return output;
visit(root, output, );
reverse(output.begin(), output.end());
return output;
}
};
▶ 第 637 题，在原来转化为二维表的基础上计算每一层的平均数，压成一维表输出
● 自己的代码，17 ms，基于第 102 题的遍历函数，输出二维表以后再一层一层计算平均数。最快的解法算法与之相同，但不再将树转化为表以后再算平均值，而是在遍历树的同时维护一个元素个数表和一个平均值表，每遍历一个非空结点就更新该层的元素个数和平均值
class Solution
{
public:
void visit(TreeNode* root, vector<vector<int>>& table, int level)
{
if (root == nullptr)
return;
if (table.size() <= level) // 首次到达该深度，建立新的一层
table.push_back(vector<int>());
visit(root->left, table, level + );
table[level].push_back(root->val);
visit(root->right, table, level + );
return;
}
vector<double> averageOfLevels(TreeNode* root)
{
vector<double> output;
if (root == nullptr)
return output;
int i, j;
double sum;
vector<vector<int>> table;
visit(root, table, );
for (i = ; i < table.size(); i++)
{
for (j = , sum = 0.0f; j < table[i].size(); j++)
sum += table[i][j];
output.push_back(sum / table[i].size());
}
return output;
}
};