問題描述 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,null,null,15,7],
3/ /9 20 / / 15 7return its zigzag level order traversal as:
[[3],[20,9],[15,7]]解決思路 參考102題，我們只需要將隊列變成棧就可以。但是這里需要考慮一個問題，就是想z型輸出，相鄰的兩層之間的左右節點push的順序也需要變換。
代碼
/** * Definition for a binary tree node. * 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) { if (root == NULL) return vector<vector<int>>(); stack<TreeNode*> cur; stack<TreeNode*> next; cur.push(root); vector<vector<int>> result; vector<int> tmp; bool flag = false; while(!cur.empty() || !next.empty()) { if (!cur.empty()) { tmp.push_back(cur.top()->val); if (!flag) { if (cur.top()->left != NULL) next.push(cur.top()->left); if (cur.top()->right != NULL) next.push(cur.top()->right); } else { if (cur.top()->right != NULL) next.push(cur.top()->right); if (cur.top()->left != NULL) next.push(cur.top()->left); } cur.pop(); } else { cur = next; next = stack<TreeNode*>(); result.push_back(tmp); tmp = vector<int>(); flag = !flag; } } result.push_back(tmp); return result; }};新聞熱點
疑難解答
