题解 | #按之字形顺序打印二叉树#
按之字形顺序打印二叉树
https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0
双端队列
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> ret;
if (pRoot == nullptr) {
return ret;
}
deque<TreeNode*> treeDeque;
treeDeque.push_back(pRoot);
int direction = 1;
while (!treeDeque.empty())
{
int num = treeDeque.size();
vector<int> lineData;
for (int i = 0; i < num; ++i)
{
if (direction)
{
TreeNode* temNode = treeDeque.front();
treeDeque.pop_front();
if(temNode->left)
{
treeDeque.push_back(temNode->left);
}
if(temNode->right)
{
treeDeque.push_back(temNode->right);
}
lineData.push_back(temNode->val);
}
else
{
TreeNode* temNode=treeDeque.back();
treeDeque.pop_back();
if(temNode->right)
{
treeDeque.push_front(temNode->right);
}
if(temNode->left)
{
treeDeque.push_front(temNode->left);
}
lineData.push_back(temNode->val);
}
}
ret.emplace_back(lineData);
direction=direction==1?0:1;
}
return ret;
}
};
