https://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
树的层序遍历
使用两个 stack 或者 vector 分别表示 当前层和下一层
/** * 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) { vector<vector<int> > ans; if(root == NULL) return ans; vector<TreeNode *> parent; vector<TreeNode *> son; parent.push_back(root); int level = 0; while(parent.empty() == false) { vector<int> ansPiece; if(level % 2 == 0) // from left to right { for(int i = parent.size() - 1; i >= 0; i--) { TreeNode *current = parent[i]; ansPiece.push_back(current->val); // save the ans if(parent[i]->left) son.push_back(parent[i]->left); if(parent[i]->right) son.push_back(parent[i]->right); } } else // from right to left { for(int i = parent.size() - 1; i >= 0; i--) { TreeNode *current = parent[i]; ansPiece.push_back(current->val); if(parent[i]->right) son.push_back(parent[i]->right); if(parent[i]->left) son.push_back(parent[i]->left); } } level++; parent = son; son.clear(); ans.push_back(ansPiece); } return ans; } };