题解 | #按之字形顺序打印二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 利用两个stack，来回保存下一层的节点，并且在各自的循环过程中进行出栈处理，就可以实现规定的之字输出；
 突破点：两个stack在同一个循环中前后顺序作为一个整体循环。
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > Print(TreeNode* pRoot) {
      vector<vector<int>> result;
      if (pRoot == nullptr)
        return result;

      stack<TreeNode*> s1;
      s1.push(pRoot);
      stack<TreeNode*> s2;
      while (!s1.empty() || !s2.empty()) {
        vector<int> vi;
        while(!s1.empty()) {
          auto cur = s1.top();
          s1.pop();
          vi.push_back(cur->val);
          if (cur->left != nullptr)
            s2.push(cur->left);
          if (cur->right != nullptr)
            s2.push(cur->right);
        }
        if (!vi.empty())
          result.push_back(vi);
        vi.clear();

        while(!s2.empty()) {
          auto cur = s2.top();
          s2.pop();
          vi.push_back(cur->val);
          if (cur->right != nullptr)
            s1.push(cur->right);
          if (cur->left != nullptr)
            s1.push(cur->left);
        }
        if (!vi.empty())
          result.push_back(vi);
      }
      return result;
    }
};