C++ two stack iterative solution


  • 0
    L
    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            if (!root)
                return true;
            stack<TreeNode*> inorder, rinorder;
            TreeNode* cur1, *cur2;
            cur1 = cur2 = root;
            while (cur1 && cur2 || !inorder.empty() && !rinorder.empty()) {
                while (cur1 && cur2) {
                    inorder.push(cur1);
                    cur1 = cur1->left;
                    rinorder.push(cur2);
                    cur2 = cur2->right;
                }
                if (!cur1 && cur2 || cur1 && !cur2)
                    return false;
                cur1 = inorder.top();
                cur2 = rinorder.top();
                inorder.pop();
                rinorder.pop();
                if (cur1 == root || cur2 == root)
                    return cur1 == cur2;
                if (cur1->val != cur2->val)
                    return false;
                cur1 = cur1->right;
                cur2 = cur2->left;
            }
            return false;
        }
    };
    

    Two stack with inorder and reverse inorder traversal.


Log in to reply
 

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