8ms C++ (both recursive and iterative) solution


  • 1
    S

    RECURSIVE SOLUTION

    class Solution {
        public:
           void recLR(TreeNode * root, vector<int> & temp){               
                if(root==NULL){
                    temp.push_back(0);
                    return;
                }
                temp.push_back(root->val);
                recLR(root->left,temp);
                recLR(root->right,temp);
            };
                      
            void recRL(TreeNode * root, vector<int> & temp){               
                if(root==NULL){
                    temp.push_back(0);
                    return;
                }               
                temp.push_back(root->val);
                recRL(root->right,temp);
                recRL(root->left,temp);
            }
            
            bool isSymmetric(TreeNode* root) {                
            vector<int> a;
            vector<int> b;
            
            recLR(root,a);
            recRL(root,b);
            
            if(equal(a.begin(),a.end(),b.begin()))
                return true;
            else 
                return false;
            } 
        };
    

    ITERATIVE SOLUTION

    bool isSymmetric(TreeNode* root) {            
        queue<TreeNode*> bfs;        
        if(!root)return true;
        if(!root->left && !root->right)return true;      
        
        TreeNode *temp = root;
        bfs.push(root);
        
        while(!bfs.empty())
        {
            int i = bfs.size();
            vector<int> row;
            
            while(i){
                temp = bfs.front();                
                if(temp!=NULL)
                    row.push_back(temp->val);
                else
                    row.push_back(0);                
                bfs.pop();                
                if(temp)
                {
                    bfs.push(temp->left);
                    bfs.push(temp->right);
                }                
                i--;
            }
            
            vector <int> rev = row;
            reverse(rev.begin(), rev.end());            
            bool res  = equal(row.begin(),row.end(), rev.begin() );            
            
            if(!res)     
                return false;
       }        
        return true;            
        }
    };

  • -4
    R

    // MY 4ms C++ ITERATIVE CODE

    class Solution {

    public:

    bool isSymmetric(TreeNode* root) {
        TreeNode * r1=root,*r2=root;
        return is_sym(r1,r2);
    }
    
    bool is_sym(TreeNode *r1,TreeNode *r2)
    {
        if(r1==NULL && r2==NULL)
        return true;
        if(r1==NULL || r2==NULL)
        return false;
        if(r1->val != r2->val)
        return false;
        return (is_sym(r1->left,r2->right) && is_sym(r1->right,r2->left));
    }
    

    };


  • 0
    Z

    I am wondering why this is ITERATIVE ... Apparently this is RECURSIVE...


Log in to reply
 

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