思路:借鉴层次遍历,设置方向标识。到每层时改变方向
vector<vector<int>> ZipPrint(TreeNode* root)
{
vector<vector<int>> seq;
if(root == NULL) return seq;
vector<int> left;
vector<int> right;
bool forward = true;
queue<TreeNode* > Q;
TreeNode* p = root;
TreeNode* last = root;
Q.push(root);
while(!Q.empty())
{
p = Q.front();
if(forward)
left.push_back(p->val);
else
right.push_back(p->val);
if(p->left)
Q.push(p->left);
if(p->right)
Q.push(p->right);
if(p == last)
{ // 一层结束
if(forward)
{
seq.push_back(left);
left.clear();
forward = false;
}
else
{
reverse(right.begin(), right.end()); // 反向,用栈也可以
seq.push_back(right);
right.clear();
forward = true;
}
last = Q.back();
}
}
return seq;
}
网友评论