给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
思路
1.需要一个变量flag标示打印方向(从左到右还是从右到左)
2.使用一个变量numOfChild标示这一层有多少个节点
#include "TreeNode.h"
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> result;
deque<TreeNode*> que;
int flag = 0, numOfChild = 1;
if (root == NULL) return result;
que.push_back(root);
while (!que.empty())
{
vector<int> temp;
for (int i = 0; i < numOfChild; i++)
{
TreeNode* node;
if (flag % 2 == 0)
{
node = que.back();
que.pop_back();
if (node->left != NULL) que.push_front(node->left);
if (node->right != NULL) que.push_front(node->right);
}
else
{
node = que.front();
que.pop_front();
if (node->right != NULL) que.push_back(node->right);
if (node->left != NULL) que.push_back(node->left);
}
temp.push_back(node->val);
}
flag++;
numOfChild = que.size();
result.push_back(temp);
}
return result;
}
};
int main(int argc, char* argv[])
{
string test = "3,9,20,null,null,15,7";
auto tree = stringToTreeNode(test);
auto res = Solution().zigzagLevelOrder(tree);
return 0;
}
