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

/*
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> > res;
        if (!pRoot)
            return res;
        queue<TreeNode*> q; // 定义队列
        q.push(pRoot); // 根结点入队列
        int level = 0;
        while (!q.empty()) {
            vector<int> arr; // 定义数组存储每一行结果
            int size = q.size(); // 当前队列长度
            for (int i = 0; i < size; i++) {
                TreeNode* tmp = q.front(); // 队头元素
                q.pop();
                // if (!tmp) // 空元素跳过
                //     continue;
                // q.push(tmp->left); // 左孩子入队列
                // q.push(tmp->right); // 右孩子入队列
                 // 只在入队时检查，避免空节点进入队列
            if (tmp->left) 
                q.push(tmp->left);
            if (tmp->right)
                q.push(tmp->right);
                if (level % 2 == 0) {
                    // 从左至右打印
                    arr.push_back(tmp->val);
                } else { // 从右至左打印
                    arr.insert(arr.begin(), tmp->val);
                }
            }
            level++; // 下一层，改变打印方向
            // if (!arr.empty())
                res.push_back(arr); // 放入最终结果
        }
        return res;
    }
};

// if (!tmp) // 空元素跳过
//     continue;
// q.push(tmp->left); // 左孩子入队列
// q.push(tmp->right); // 右孩子入队列  
和 
// if (!arr.empty())配套使用

因为左右孩子可能为空,导致空指针进入队列

如果没有// if (!tmp) // 空元素跳过
       //     continue;
就可能导致空操作

如果没有// if (!arr.empty())配套使用
就会在结果后面多输出一个空数组

但更好的做法是从根本上避免产生空数组
改进方案：在入队时避免空节点
 if (tmp->left) 
      q.push(tmp->left);
if (tmp->right)
      q.push(tmp->right);