题解 | #求二叉树的层序遍历#

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    //二叉树的层序遍历也被称为广度优先遍历
    //本题和一般的二叉树层序遍历唯一的区别就在于怎么判断什么时候该换行了
    //换句话说就是怎么知道哪些节点是在同一行的
    //事实上，最后进入队列的节点就是下一行的分界点
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        vector<vector<int> >A;
        vector<int> B;
        if(root==NULL)
            return A;
        TreeNode*curLast=root,*nextLast=NULL;//两个变量，第一个是当前行的最后一个节点。第二个是下一行的最后一个节点
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){//队列非空时
            TreeNode*node=que.front();
            que.pop();
            if(node->left){
                que.push(node->left);
                nextLast=node->left;//更新nextLast
            }
            if(node->right){
                que.push(node->right);
                nextLast=node->right;//更新nextLast
            }
            B.push_back(node->val);
            if(node==curLast){//说明当前节点已经是当前行的最后一个节点了，下一个节点就是下一行的了
                A.push_back(B);
                B.clear();
                curLast=nextLast;
            }
        }
        return A;
    }
};