题目链接
Binary Tree Zigzag Level Order Traversal - LeetCode
注意点
- 不要访问空结点
解法
解法一：递归，递归，在Binary Tree Level Order Traversal - LeetCode的基础上将奇数层（下标从0开始）结果逆序即可。
/**
* 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:
typedef vector<vector<int>> v;
typedef TreeNode* node;
void bfs(int level,node n,v& ret)
{
if(ret.size() == level) ret.push_back({});
ret[level].push_back(n->val);
if(n->left) bfs(level+1,n->left,ret);
if(n->right) bfs(level+1,n->right,ret);
}
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
v ret;
if(!root) return ret;
bfs(0,root,ret);
int i = 0,n = ret.size();
for(i = 0;i < n;i++)
{
if(i%2 == 1) reverse(ret[i].begin(),ret[i].end());
}
return ret;
}
};
解法二：非递归，同样在Binary Tree Level Order Traversal - LeetCode的基础上访问到奇数层时结果逆序即可。
/**
* 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:
typedef vector<vector<int>> v;
typedef TreeNode* node;
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
v ret;
if(!root) return ret;
int level = 0;
queue<node> q;
q.push(root);
while(!q.empty())
{
vector<int> aLevel;
for(int i = q.size();i > 0;--i)
{
node n = q.front();
q.pop();
aLevel.push_back(n->val);
if(n->left) q.push(n->left);
if(n->right) q.push(n->right);
}
if(level%2 == 1) reverse(aLevel.begin(),aLevel.end());
ret.push_back(aLevel);
level++;
}
return ret;
}
};