Leetcode 103. Binary Tree Zigzag Level Order Traversal (cpp)

题目

解法1：DFS

class Solution {
    
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> ans;dfs(ans,root,0);for(int i = 0;i<ans.size();i++){
    if(i % 2 == 0) continue;for(int j = 0, k=ans[i].size()-1;j<=k;j++,k--){
    swap(ans[i][j],ans[i][k]);}}return ans;}void dfs(vector<vector<int>>& ans, TreeNode* node, int level){
    if(!node) return;if(ans.size() <= level){
    ans.push_back({
    });}ans[level].push_back(node->val);dfs(ans,node->left,level+1);dfs(ans,node->right,level+1);}
};

解法2：BFS

class Solution {
    
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    if(!root) return {
    };vector<vector<int>> res;queue<TreeNode*> q;q.push(root);TreeNode* node;int level = 0;int level_len;while(!q.empty()){
    res.push_back({
    });level_len = q.size();for(int i=0;i<level_len;i++){
    node = q.front();res[level].push_back(node->val);q.pop();if(node->left){
    q.push(node->left);}if(node->right){
    q.push(node->right);}}level++;}for(int i = 0;i<res.size();i++){
    if(i % 2 == 0) continue;for(int j = 0, k=res[i].size()-1;j<=k;j++,k--){
    swap(res[i][j],res[i][k]);}}return res;}
};