Share my solution O(1) spaces, 9ms, recursion


  • 0
    P
    class Solution {
    

    public:
    vector<vector<int> > levelOrder(TreeNode *root) {
    vector<vector<int>> result;
    if (!root)
    return result;

        vector<int> level;
        level.push_back(root->val);
        result.push_back(level);
        
        getNodeOrder(root, 1, result);
        return result;
    }
    
    void getNodeOrder(TreeNode *node, int deep, vector<vector<int>> &result) {
        vector<int> level, tmp;
        TreeNode *left, *right;
        
        left = node->left;
        right = node->right;
        
        if (left) 
            level.push_back(left->val);
            
        if (right) 
            level.push_back(right->val);
            
        if (level.empty())
            return;
            
        if (result.size() == deep) {
            result.push_back(level);
        } else {
            result[deep].insert(result[deep].end(), level.begin(), level.end());
        }
            
        if (left)
            getNodeOrder(left, deep + 1, result);
            
        if (right)
            getNodeOrder(right, deep + 1, result);
    }
    

    };


  • 2
    F

    I think your solution might also be O(n) space, because recursive itself is inherent space consumer. every time you call this function you need create a pointer in stack which point to the new function. You created new function N times, thus your space complexity might be also O(n).


Log in to reply
 

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