#牛客网 剑指offer-按之字形顺序打印二叉树

一、题目

解法一、队列+遍历

class Solution {
public:
    vector > Print(TreeNode* pRoot)
    {
        vector> ret;
        if(pRoot == nullptr) return ret;
        queue q;
        int index = 0;
        q.push(pRoot);
        
        while(q.empty()==0)
        {
            int sz = q.size();
            vector ans;
            while(sz--)
            {
                TreeNode *node = q.front();
                q.pop();
                ans.push_back(node->val);
                
                if(node->left != nullptr) q.push(node->left);
                if(node->right != nullptr) q.push(node->right);
            }
            index++;
            if((index&1) != 1) reverse(ans.begin(),ans.end());
            ret.push_back(ans);
        }
        return ret;
    }    
};

C++向量vector类

push_back()在向量最后插入元素

reverse(str.begin(),str.end())反转数组，也可以反转字符串

C++队列Queue类成员函数如下:

queue q;建立元素为int类型的队列。

back() 返回最后一个元素

empty() 如果队列空则返回真

front() 返回第一个元素

pop() 删除第一个元素

push() 在末尾加入一个元素

size() 返回队列中元素的个数

注意队列栈向量等类的灵活运用。

 n&1可用于判断n是否为奇数。&表示按位与运算，n转换为二进制与1按与运算，最低位为1则n&1=1,奇数；反之为偶数。