C++ Iterative solution use stack


  • 0
    Q

    If you are familiar with stack-based iterative solution, this is just an application of it.
    Note we return in the middle of the tree when both stacks pop the root.

    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            if(!root) return true;
          stack<TreeNode*> s1, s2;
          TreeNode* ptr1=root, *ptr2=root;
          while((ptr1&&ptr2) || (!s1.empty()&&!s2.empty()))
          {
              if(ptr1 && ptr2) {
                  if(ptr1->val != ptr2->val) return false;
                  s1.push(ptr1); s2.push(ptr2);
                  ptr1= ptr1->left; ptr2 = ptr2->right;
              } else 
              if(!ptr1 && !ptr2) {
                  if(!s1.empty() && !s2.empty()) {
                      if(s1.top() == root && s2.top() == root) return true;
                      ptr1 = s1.top()->right; ptr2 = s2.top()->left;
                      s1.pop() ; s2.pop();
                  } else if( (s1.empty()&&!s2.empty() ) || (!s1.empty()&&s2.empty()))
                  return false;
                  
                  
              } else
              {
                  return false;
              }
              
          }
          return true;
        }
    };```

Log in to reply
 

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