力扣剑指offer32—从上到下打印二叉树

力扣剑指offer32—从上到下打印二叉树         这三个题目大致上都相同，I的做法最简单，II是在I的基础上做了相当于换行的 *** 作，III在II的基础上对偶数行的元素进行了反转

剑指offer32-I、从上到下打印二叉树

class Solution {
public:
    vector levelOrder(TreeNode* root) {
        if(root==nullptr)return {};//判空
        queueque;//层次遍历属于广度优先搜索，用队列来存储
        que.push(root);//将根结点放入队列
        vector vec;
        while(!que.empty()){//当队列不为空，d出队首元素，并且，将该元素插入数组
            TreeNode *res=que.front();//res节点指向队列第一个元素
            que.pop();
            vec.push_back(res->val);
            if(res->left){//如果当前节点有左孩子，左孩子入队
                que.push(res->left);
            }
            if(res->right){//如果当前节点有右孩子，右孩子入队
                que.push(res->right);
            }
        }
        return vec;
    }
};

---

剑指offer32-II、从上到下打印二叉树

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        if(root==nullptr)return {};
        vector>vec;
        queueque;
        TreeNode *last=root;//标记二叉树当前行的最后一个节点
        TreeNode *nlast=nullptr;//下一行的最后一个节点
        que.push(root);
        int i=0;
        vec.push_back({});//二维数组新增一行
        while(!que.empty()){
            TreeNode *res=que.front();
            que.pop();
            vec[i].push_back(res->val);
            if(res->left){
                que.push(res->left);
                nlast=res->left;
            }
            if(res->right){
                que.push(res->right);
                nlast=res->right;
            }
            if(res==last){
                last=nlast;//
                vec.push_back({});//每到二叉树最后一个元素之后就给二维数组添加一行
                i++;//用i做标记，数组元素要添加到vec[i]行
            }
        }
        vec.pop_back();//删除二维数组中最后多加的一行一维数组
        return vec;
    }
};

---

 剑指offer32-III、从上到下打印二叉树

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        if(root==nullptr)return {};
        vector>vec;
        queueque;
        TreeNode *last=root;//标记二叉树当前行的最后一个节点
        TreeNode *nlast=nullptr;//下一行的最后一个节点
        que.push(root);
        int i=0;
        vec.push_back({});//二维数组新增一行
        while(!que.empty()){
            TreeNode *res=que.front();
            que.pop();
            vec[i].push_back(res->val);
            if(res->left){
                que.push(res->left);
                nlast=res->left;
            }
            if(res->right){
                que.push(res->right);
                nlast=res->right;
            }
            if(res==last){
                if(i%2!=0){//i为奇数时当前行需要被翻转
                    reverse(vec[i].begin(),vec[i].end());
                }
                last=nlast;
                vec.push_back({});//每到二叉树最后一个元素之后就给二维数组添加一行
                i++;//用i做标记，数组元素要添加到vec[i]行
            }
        }
        vec.pop_back();//删除二维数组中最后多加的一行一维数组
        return vec;
    }
};