[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--;
    }
};

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--;

}

};

[LEETCODE]Binary Tree Zigzag Level Order Traversal

請按讚：

相關

發表者：user

分享此文：

請按讚：

相關

發表者：user