[LeetCode] Binary Tree Zigzag Level Order Traversal

這題是上一題的延伸

以為這題變化後要用BFS做

(如果要省時間的確要這樣)

因為看到discuss看到有人說 可以one queue without reversing….

害我想惹很久，結果點進去不出所料

還是有用其他空間(vector…)

如果用雙向的linkedlist做 才能達到省空間又省時間的作法吧

後來我就懶了 直接把奇數行reverse就好了 直接用algorithm的API幫你做好XD

class Solution {
public:
    
    vector<vector<int>> ans;
    int level = 0;
    
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        
        if(root == NULL)
            return ans;
        else
            preorder(root);

        int len = ans.size();
        
        for(int i = 1; i < len ; i += 2) {            
            reverse(ans[i].begin(),ans[i].end());
        }
        
        return ans;
    }
    
    
    void preorder(TreeNode* node)
    {
        
        if(node == NULL)
            return;
        
        level++;                
        
        if(ans.size() < level)
            ans.push_back(vector<int>());    
        ans[level-1].push_back(node->val);     
        
        preorder(node->left);                
        preorder(node->right);
        
        level--;
    }
};