A Straightforward Quick Solution Only Reverse the Odd Line after Level Traversal


  • 0
    N

    The idea is simple and the running time is about 10ms.

    vector<vector<int> > result;
    
    void reverseOddLine() {
        for(int i = 1; i < result.size(); i += 2)
           reverse(result[i].begin(), result[i].end());
    }
    
    void levelTraversal(TreeNode *root, int level) {
        if(root == NULL)
            return;
        if(result.size() == level)
            result.push_back(vector<int> ());
    
        result[level].push_back(root->val);
        levelTraversal(root->left,  level + 1);
        levelTraversal(root->right, level + 1);
    }
    
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        levelTraversal(root, 0);    // Level Traverse the whole tree
        reverseOddLine();           // Reverse the odd Line
        return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.