Iterative Solution using a stack


  • 0
    C
    class Solution {
    public:
        bool isSymmetric(TreeNode* root) 
        {
            stack<TreeNode*> nodes_l2r;
            stack<TreeNode*> nodes_r2l;
            nodes_l2r.push(root);
            nodes_r2l.push(root);
            
            while( !nodes_r2l.empty() )
            {
                TreeNode *n1 = nodes_l2r.top();
                TreeNode *n2 = nodes_r2l.top();
                
                if(!n1 && !n2) 
                {
                    nodes_l2r.pop();
                    nodes_r2l.pop();
                    continue;
                }
                if(n1 && !n2) return false;
                if(!n1 && n2) return false;
                
                if(n1->val != n2->val) return false;
                
                nodes_l2r.pop(); 
                nodes_r2l.pop();
                
                nodes_l2r.push(n1->left);
                nodes_l2r.push(n1->right);
                
                nodes_r2l.push(n2->right);
                nodes_r2l.push(n2->left);
            }
            
            return true;
        }
    };

Log in to reply
 

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