請實(shí)現(xiàn)一個函數(shù)按照之字形順序從上向下打印二叉樹。
即第一行按照從左到右的順序打印潮峦，第二層按照從右到左的順序打印或舞，第三行再按照從左到右的順序打印，其他行以此類推蔼囊。
樣例
輸入如下圖所示二叉樹[8, 12, 2, null, null, 6, 4, null, null, null, null]
8
/ \
12 2
/ \
6 4
輸出：[[8], [2, 12], [6, 4]]
分析：
(BFS) O(n)
在上一道題《分行從上往下打印二叉樹》 的基礎(chǔ)上修改代碼焚志。
增加一個行號標(biāo)記i，偶數(shù)行直接reverse一下
時間復(fù)雜度分析：每個點(diǎn)遍歷一次畏鼓，所以時間復(fù)雜度是 O(n)
/**
* 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>> printFromTopToBottom(TreeNode* root) {
vector<vector<int>> res;//二維數(shù)組用于存放結(jié)果元素
queue<TreeNode*> q;//定義一個隊(duì)列來模擬BFS
if(!root) return res;//根元素為空酱酬，什么也不做，直接返回res
q.push(root);//把根節(jié)點(diǎn)放入隊(duì)列中
int i = 1; //i用來記錄行號
q.push(nullptr);//NULL作為行末尾標(biāo)記
vector<int> cur;// cur用來存放當(dāng)前行的元素
while(q.size()) {//隊(duì)列中只要還有元素就進(jìn)行操作
auto x = q.front();//訪問隊(duì)首元素
q.pop();//刪掉隊(duì)首元素
if(x) {//x為true云矫，說明該行還有元素需要操作
cur.push_back(x->val);// 當(dāng)前元素存入cur中
if(x->left) q.push(x->left);//將左兒子放入隊(duì)列中
if(x->right) q.push(x->right);//將右兒子放入隊(duì)列中
} else {//x為false膳沽，說明已經(jīng)訪問行尾標(biāo)志NULL
if (q.size()) q.push(nullptr);//行元素已經(jīng)在隊(duì)列中了，這是增加新的行標(biāo)記NULL
if(i % 2 == 0) reverse(cur.begin(), cur.end()); //偶數(shù)行的元素翻轉(zhuǎn)一下
res.push_back(cur); //把當(dāng)前行的元素存放在結(jié)果數(shù)組中
cur.clear();//把當(dāng)前行的元素清空
i++;// 當(dāng)前行完成让禀，行號加1
}
}
return res;
}
}
