102. 二叉树的层序遍历
难度：中等
题目
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]
解题：
实际上就是广度优先遍历，只不过需要记录每一层的个数。
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> vecResult;
if(root == nullptr)
return vecResult;
queue<TreeNode*> q;
q.push(root);
int iTemp;
TreeNode* pTemp = nullptr;
while(!q.empty())
{
iTemp = q.size();
vecResult.push_back(vector<int>());
while(iTemp--)
{
pTemp = q.front();
q.pop();
vecResult.back().push_back(pTemp->val);
if(pTemp->left)
q.push(pTemp->left);
if(pTemp->right)
q.push(pTemp->right);
}
}
return vecResult;
}
};
107. 二叉树的层序遍历 II
难度：中等
题目
给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其自底向上的层序遍历为：
[
[15,7],
[9,20],
[3]
]
解题
该题在上一个题的基础上，加一个容器反转就可以解决。
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> vecResult;
if(root == nullptr)
return vecResult;
queue<TreeNode*> q;
q.push(root);
int iTemp;
TreeNode* pTemp = nullptr;
while(!q.empty())
{
iTemp = q.size();
vecResult.push_back(vector<int>());
while(iTemp--)
{
pTemp = q.front();
q.pop();
vecResult.back().push_back(pTemp->val);
if(pTemp->left)
q.push(pTemp->left);
if(pTemp->right)
q.push(pTemp->right);
}
}
reverse(vecResult.begin(),vecResult.end());
return vecResult;
}
};
103. 二叉树的锯齿形层序遍历
难度：中等
题目
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层序遍历如下：
[
[3],
[20,9],
[15,7]
]
解题
这道题也是在第一道基础上进行变化，需要添加一个标志位判断当前行是以什么顺序打印。
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> vecResult;
if(root == nullptr)
return vecResult;
queue<TreeNode*> q;
q.push(root);
int iSize;
TreeNode* pTemp = nullptr;
bool bLeft2Right = true;
while(!q.empty())
{
iSize = q.size();
vecResult.push_back(vector<int>(iSize));
for(int i = 0; i < iSize; ++i)
{
pTemp = q.front();
q.pop();
if(bLeft2Right)
{
vecResult.back()[i] = pTemp->val;
}
else
{
vecResult.back()[iSize - 1 - i] = pTemp->val;
}
if(pTemp->left)
q.push(pTemp->left);
if(pTemp->right)
q.push(pTemp->right);
}
bLeft2Right = !bLeft2Right;
}
return vecResult;
}
};
|