lintcode二叉樹的鋸齒形層次遍歷 （雙端隊列）

?

題目鏈接：

　　http://www.lintcode.com/zh-cn/problem/binary-tree-zigzag-level-order-traversal/

二叉樹的鋸齒形層次遍歷?

　　給出一棵二叉樹，返回其節點值的鋸齒形層次遍歷（先從左往右，下一層再從右往左，層與層之間交替進行）?

樣例

　　給出一棵二叉樹?{3,9,20,#,#,15,7},

   　　 3/ \9  20/  \15   7

　　返回其鋸齒形的層次遍歷為：

　　[[3],[20,9],[15,7]]

思路：

　　我們用雙端隊列模擬一下這個過程：開始的時候是正向遍歷，3通過push_front()放入隊列Q， 形成Q[3]。接著我們規定正向遍歷的時候從隊列前端去元素，下一層元素放入隊列的時候是放入隊列的后端；而反向遍歷的時候正好相反，唯一不同的就是反向遍歷時，下一層的右孩子結點（如果有）先放入隊列的前端。

　　開始Q[3](從前端取數字), 然后下一層放入后是Q[9,20](從后端去數字)，20的下一層放入后是Q[15,7,9], 然后變成Q[15,7](從前端去數字)，最后得到遍歷的結果。

代碼實現：

/*** Definition of TreeNode:* class TreeNode {* public:*     int val;*     TreeNode *left, *right;*     TreeNode(int val) {*         this->val = val;*         this->left = this->right = NULL;*     }* }*/class Solution {/*** @param root: The root of binary tree.* @return: A list of lists of integer include *          the zigzag level order traversal of its nodes' values */
public:vector<vector<int>> zigzagLevelOrder(TreeNode *root) {// write your code herevector<vector<int>> vv;if(root == NULL) return vv;deque<TreeNode *> q;q.push_back(root);bool dir = true;//true表示從左向右存儲層次遍歷，否則是從右向左int levelCnt = 1;//上一層的節點數目int curLevelCnt = 0;//下一層節點數目vector<int> v;while(!q.empty()){TreeNode *cur;if(dir){cur = q.front();q.pop_front();} else {cur = q.back();q.pop_back();}if(dir){if(cur->left){q.push_back(cur->left);++curLevelCnt;}if(cur->right){q.push_back(cur->right);++curLevelCnt;}} else {if(cur->right){q.push_front(cur->right);++curLevelCnt;}if(cur->left){q.push_front(cur->left);++curLevelCnt;}}v.push_back(cur->val);--levelCnt;if(levelCnt == 0){//這一層完畢
                vv.push_back(v);v.clear();levelCnt = curLevelCnt;curLevelCnt = 0;dir = !dir;}}return vv;}
};

?