LeetCode 从上到下打印链表

题目描述

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如: 给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

解题想法

这道题本身并不是什么难题，也很明显可以看出是一个层序遍历的变种，解决问题的关键就在于如何区分当前层和下一层，最开始是打算使用pair将每个结点与其相应的层序号对应起来。但在实际写代码时发现有点困难，最后还是去翻了题解，发现了利用空指针作为层与层之间分隔的方法。具体做法就是在第一次入队时再入队一个空指针，之后利用队头元素不为空指针作为内循环的判断，如果队头为空，则表明了已经循环完了一层。而由于二叉树的特点，在使用层序遍历时，遍历完一层也即代表着下一层的非空结点已经完全入队，这时便可以再入队一个空指针作为下一个分隔结点。利用这样的循环就能做到以层为序来打印层序遍历。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (root == NULL) {
            return res;
        }
        queue<TreeNode*> que;  // 用于层序遍历
        que.push(root);
        que.push(NULL);  // 利用空指针作为每层之间的分隔
        while (que.size()) {
            vector<int> vtemp;  // 队列不为空时，就申请空间存储本层数据
            while (que.front()) {  // 用这个条件判断是否属于同一层数据
                TreeNode *temp = que.front();
                vtemp.push_back(temp->val);
                que.pop();
                if (temp->left) que.push(temp->left);
                if (temp->right) que.push(temp->right);
            }
            // 退出上面的循环表示已经到了层与层之间的界线
            que.pop();
            if (que.size()) {  // 如果此时队列非空，则表明不是最后一层
                // 遍历过一层即表示队列中已经保存了下一层，因此需要加入空指针分割
                que.push(NULL);
            }
            res.push_back(vtemp);
        }
        return res;
    }
};