Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7}
,
3 / \ 9 20 / \ 15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7] ]
思路:层序遍历的改进。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int> > zigzagLevelOrder(TreeNode *root) { deque<TreeNode*> Q1,Q2; vector<vector<int> > res; res.clear(); if (root == NULL) { return res; } Q1.push_back(root); vector<int> perRes; perRes.push_back(Q1.back()->val); res.push_back(perRes); int i = 0; while(!Q1.empty()) { Q2.clear(); while(!Q1.empty()) { TreeNode* pNode = Q1.front(); Q1.pop_front(); if (pNode->left != NULL) { Q2.push_back(pNode->left); } if (pNode->right != NULL) { Q2.push_back(pNode->right); } } perRes.clear(); i++; Q1 = Q2; if (i&1) { while(!Q2.empty()) { perRes.push_back(Q2.back()->val); Q2.pop_back(); } } else { while(!Q2.empty()) { perRes.push_back(Q2.front()->val); Q2.pop_front(); } } if (!perRes.empty()) { res.push_back(perRes); } } return res; } };