[leetcode] 103 Binary Tree Zigzag Level Order Traversal (Medium)

原题链接

题目要求以“Z”字型遍历二叉树,并存储在二维数组里。

利用BFS,对每一层进行遍历。对于每一层是从左还是从右,用一个整数型判断当前是偶数行还是奇数行就可以了。

class Solution
{
public:
vector<vector<int>> res;
vector<vector<int>> zigzagLevelOrder(TreeNode *root)
{
if (root == NULL)
return res;
stack<TreeNode *> sta;
sta.push(root);
TravelNextLevel(sta, 1);
return res;
} private:
void TravelNextLevel(stack<TreeNode *> &sta, int level)
{
res.emplace_back();
res.back().reserve(sta.size());
stack<TreeNode *> nextSta;
while (!sta.empty())
{
TreeNode *curNode = sta.top();
sta.pop();
res.back().push_back(curNode->val);
if (level % 2 != 0)
{
if (curNode->left)
nextSta.push(curNode->left);
if (curNode->right)
nextSta.push(curNode->right);
} if (level % 2 == 0)
{
if (curNode->right)
nextSta.push(curNode->right);
if (curNode->left)
nextSta.push(curNode->left);
}
} if (!nextSta.empty())
TravelNextLevel(nextSta, level + 1);
}
};
上一篇:AC日记——绿豆蛙的归宿 codevs 2488


下一篇:MVC5知识点记录