題目描述:
給定一個二叉樹,傳回其節點值的鋸齒形層次周遊。(即先從左往右,再從右往左進行下一層周遊,以此類推,層與層之間交替進行)。
例如:
給定二叉樹 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
傳回鋸齒形層次周遊如下:
[
[3],
[20,9],
[15,7]
]
此題目思路同二叉樹的層序周遊,先按照層序周遊将整個二叉樹周遊一遍,最後将得到的結果偶數層的vector進行reverse即可
/**
* 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>> zigzagLevelOrder(TreeNode* root) {
queue<TreeNode*> que;
vector<vector<int>> res;
if(root==NULL)
return {};
que.push(root);
while(!que.empty()){
int size=que.size();//得到這一層有幾個節點
vector<int> level;
while(size--){
TreeNode* now=que.front();
que.pop();
if(now->left)
que.push(now->left);
if(now->right)
que.push(now->right);
level.push_back(now->val);
}
res.push_back(level);
}
for(int i=1;i<res.size();i+=2)
reverse(res[i].begin(),res[i].end());
return res;
}
};
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAnYldHL0FWby9mZvwFN4ETMfdHLkVGepZ2XtxSZ6l2clJ3LcV2Zh1Wa9M3clN2byBXLzN3btgHL9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsQTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5iN1IDOxMTZkZTZlFWO4AjNzYzX2ITM1ATMxAzLcFTMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)
/**
* 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>> zigzagLevelOrder(TreeNode* root) {
if(root==nullptr)
return {};
vector<vector<int>> res;
stack<TreeNode*> level[2];
int current=0;
int next=1;
level[current].push(root);
vector<int> temp;
while(!level[0].empty()||!level[1].empty()){
TreeNode* Node=level[current].top();
level[current].pop();
temp.push_back(Node->val);
if(current==0){//奇數層,從左向右加入子節點
if(Node->left)
level[next].push(Node->left);
if(Node->right)
level[next].push(Node->right);
}
else{//偶數層從右向左加入子節點
if(Node->right)
level[next].push(Node->right);
if(Node->left)
level[next].push(Node->left);
}
if(level[current].empty()){//一層結束後,将更新current和next的值,并将這一層的結果放入到res中
current=1-current;
next=1-next;
res.push_back(temp);
temp.clear();
}
}
return res;
}
};