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

在层次遍历上的一个简单应用

/*
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) {
        //  翻转序列的标志
      int flag = 1; 
      std::queue<TreeNode *> queue_;
      std::vector<std::vector<int>> res;
      
      if (pRoot == nullptr) {
        return res;
      }
      
      queue_.push(pRoot);
      
      while (!queue_.empty()) {
        int size = queue_.size();
        std::vector<int> tmp;
        
        for (int i = 0; i < size; ++i) {
          TreeNode *ptr = queue_.front();
          queue_.pop();
          tmp.push_back(ptr->val);
          if (ptr->left) {
            queue_.push(ptr->left);
          }
          if (ptr->right) {
            queue_.push(ptr->right);
          }
        }
        
        if (flag % 2 == 0) {
          reverse(tmp.begin(), tmp.end());
        }
        
        ++flag;
        res.emplace_back(std::move(tmp));
      }
      
      return res;
    }
    
};