Why the time cost reduce to 4ms from 8ms when I manually do resverse in both dfs and bfs approach?


  • 0
    Q

    // dfs

    class Solution {
        void dfs(TreeNode *root, int level, vector<vector<int>> &res) {
            if(level==res.size()) res.push_back(vector<int>());
            res[level].push_back(root->val);
            if(root->left) dfs(root->left,level+1,res);
            if(root->right) dfs(root->right,level+1,res);
        }
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            vector<vector<int>> res;
            if(root) dfs(root,0,res);
    		//std::reverse(res.begin(),res.end()); // 8ms
    		for(int i=0,j=res.size()-1;i<j;++i,--j) std::swap(res[i],res[j]); // 4ms
            return res;
        }
    };
    

    // bfs

    class Solution {
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            vector<vector<int>> res;
            if(root) {
                std::queue<TreeNode*> que;
                vector<int> row;
                que.push(root);
                while(!que.empty()) {
                    int cnt=que.size();
                    while(cnt-->0) {
                        root=que.front();
                        que.pop();
                        row.push_back(root->val);
                        if(root->left) que.push(root->left);
                        if(root->right) que.push(root->right);
                    }
                    res.push_back(vector<int>());
                    std::swap(row,res.back());
                }
    			//std::reverse(res.begin(),res.end()); // 8ms
    			for(int i=0,j=res.size()-1;i<j;++i,--j) std::swap(res[i],res[j]); // 4ms
            }
            return res;
        }
    };

Log in to reply
 

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