二叉树的S型遍历（双栈）

思路：维护两个栈，逻辑如下：

• 奇数层的遍历明显从右到左，其下一层反向所以这层入栈的子树也应该从右到左
• 偶数层反向
  注意在维护STL的时候指针参数地传递，关于对象的赋值要处理好，可以用指针减少不必要的麻烦！
• 在处理遍历方向时候通过根节点加入不同的栈能够完成顺序地完全对称遍历，也就是本来是之字形遍历变为S型遍历

Code：

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > ans;
        ans.clear();
        stack<TreeNode*> st1, st2;
        while (!st1.empty()) st1.pop();
        while (!st2.empty()) st2.pop();
         if (!pRoot) return ans;
        st1.push(pRoot);
        while (!st1.empty() || !st2.empty()) {
            vector<int> tmp;
            tmp.clear();
            if (!st1.empty()) {
                while (!st1.empty()) {
                    TreeNode* vis = st1.top();
                    st1.pop();
                    tmp.push_back(vis->val);                    
                    if (vis->left) st2.push(vis->left);
                    if (vis->right) st2.push(vis->right);
                }
            } else {
                while (!st2.empty()) {
                    TreeNode* vis = st2.top();
                    st2.pop();
                    tmp.push_back(vis->val);                    
                    if (vis->right) st1.push(vis->right);
                    if (vis->left) st1.push(vis->left);
                }
            }
            ans.push_back(tmp);
        }
        return ans;
    }
     
};