queue的方式

    1. /**
    2.  * Definition for a binary tree node.
    3.  * struct TreeNode {
    4.  *     int val;
    5.  *     TreeNode *left;
    6.  *     TreeNode *right;
    7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    8.  * };
    9.  */
    10. class Solution {
    11. public:
    12.     vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    14.         vector<vector<int>> res;
    15.         if(!root) return res;
    16.         vector<int> path;
    17.         queue<TreeNode*> q;
    18.         q.push(root);
    19.         q.push(nullptr);
    20.         int cnt = 0;
    21.         while(q.size())
    22.         {
    23.             auto tmp = q.front();
    24.             q.pop();
    25.             if(tmp)
    26.             {
    27.                 path.push_back(tmp->val);
    28.                 if(tmp->left) q.push(tmp->left);
    29.                 if(tmp->right) q.push(tmp->right);
    30.             }
    31.             else
    32.             {
    33.                 if(cnt % 2 != 0)
    34.                     reverse(path.begin(), path.end());
    35.                 res.push_back(path);
    36.                 path.clear();
    37.                 cnt++;
    38.                 if(!q.size()) break;
    39.                 q.push(nullptr);
    40.             }
    41.         }
    42.         return res;
    43.     }
    44. };

    DFS

    /**
 * 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 {
    vector<vector<int>> res;
    void dfs(TreeNode* root, int level)
    {
        if(!root) return;
        if(res.size() < level + 1)
        {
            int cnt = level + 1 - res.size();
            while(cnt--) res.push_back({});
        }
        res[level].push_back(root->val);
        dfs(root->left, level + 1);
        dfs(root->right, level + 1);
    }
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        dfs(root, 0);
        for(int i = 1; i < res.size(); i += 2)
            reverse(res[i].begin(), res[i].end());
        return res;
    }
};

    第二次写题

    /**
 * 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) {
        vector<vector<int>> res;
        if(!root) return res;
        vector<int> line;
        queue<TreeNode*> q;
        int level = 0;
        q.push(root);
        q.push(nullptr);
        while(q.size())
        {
            TreeNode* tmp = q.front();
            q.pop();
            if(!tmp)
            {
                if(level) reverse(line.begin(), line.end());
                res.push_back(line);
                line.clear();
                level ^= 1;
                if(!q.size()) break;
                q.push(nullptr);
            }
            else
            {
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
                line.push_back(tmp->val);
            }
        }
        return res;
    }
};