Why I got memory exceeded on this solution?


  • 0
    Y

    /**

    • Definition for binary tree
    • struct TreeNode {
    • int val;
      
    • TreeNode *left;
      
    • TreeNode *right;
      
    • TreeNode(int x) : val(x), left(NULL), right(NULL) {}
      
    • };
      */

    // -999 is the special value for empty node

    struct DepthNode
    {
    TreeNode* node;
    int depth;
    };

    class Solution {
    private:
    bool IsValid(vector< int > & vec)
    {
    if (vec.size() < 1)
    return true;

        int i=0;
        int j=vec.size()-1;
        
        while (i<j)
        {
            if (vec[i++]!=vec[j--])
                return false;
        }
        
        return true;
    }
    
    void PushTreeNodeToBFS(queue< DepthNode > & BFS, TreeNode* ptr, int depth)
    {
        DepthNode n;
        if (ptr)
        {
            n.node = ptr;
            n.depth = depth;
        }
        else
        {
            TreeNode* emp = new TreeNode(-999);
            n.node = emp;
            n.depth = depth;
        }
        
        BFS.push(n);
    }
    

    public:
    bool isSymmetric(TreeNode *root) {
    if (!root)
    return true;

        queue< DepthNode > BFS;
        vector <int> level_val_vec;
        
        DepthNode n;
        n.node = root;
        n.depth = 1;
        BFS.push(n);
        
        int current_level = 0;
        
        while (!BFS.empty())
        {
            int level = BFS.front().depth;
            TreeNode* ptr = BFS.front().node;
            
            // Check symmetric in the current level
            if (level > current_level)
            {
                if (!IsValid(level_val_vec))
                {
                    return false;
                }
                else
                {
                    level_val_vec.clear();
                }
                current_level = level;
            }
            
            level_val_vec.push_back(ptr->val);
            
            if (ptr->val != -999)
            {
                PushTreeNodeToBFS(BFS, ptr->left, level + 1);
                PushTreeNodeToBFS(BFS, ptr->right, level + 1);
            }
            else
            {
                delete ptr;
            }
        }
        
        if (!IsValid(level_val_vec))
            return false;
            
        return true;
        
    }
    

    };


Log in to reply
 

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