[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); } };

转载于:https://www.cnblogs.com/ruoh3kou/p/9893412.html