描述

給定一個二叉樹，返回該二叉樹的之字形層序遍歷，（第一層從左向右，下一層從右向左，一直這樣交替）

數(shù)據(jù)范圍：0 \le n \le 15000≤n≤1500,樹上每個節(jié)點的val滿足?|val| <= 100∣val∣<=100
要求：空間復雜度：O(n)O(n)，時間復雜度：O(n)O(n)

例如：
給定的二叉樹是{1,2,3,#,#,4,5}

該二叉樹之字形層序遍歷的結果是

[

[1],

[3,2],

[4,5]

]

示例1

輸入：

{1,2,3,#,#,4,5}

返回值：

[[1],[3,2],[4,5]]

說明：

如題面解釋，第一層是根節(jié)點，從左到右打印結果，第二層從右到左，第三層從左到右。

示例2

輸入：

{8,6,10,5,7,9,11}

返回值：

[[8],[10,6],[5,7,9,11]]

示例3

輸入：

{1,2,3,4,5}

返回值：

[[1],[3,2],[4,5]]

?解題報告：

可以像代碼里一樣，用兩個隊列。或者用一個隊列+一個cnt來保存某一層的節(jié)點個數(shù)。

/* struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {} }; */ class Solution { public:vector<vector<int> > Print(TreeNode* pRoot) {vector<vector<int> > ans;if(!pRoot) return ans;queue<TreeNode* > q[2];int flag = 0;q[flag].push(pRoot);while(q[flag].size()) {vector<int> t;while(q[flag].size()) {TreeNode* cur = q[flag].front();q[flag].pop();t.push_back(cur->val);if(cur->left) q[!flag].push(cur->left);if(cur->right) q[!flag].push(cur->right);}if(flag) reverse(t.begin(), t.end());ans.push_back(t);flag = !flag;}return ans;}};

總結

以上是生活随笔為你收集整理的【NC14 按之字形顺序打印二叉树】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。