class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        return root ? isSymmetric(root->left, root->right) : true;
    }

private:
    bool isSymmetric(TreeNode *left, TreeNode *right) {
        if (!left && !right) return true;
        if ( left && !right) return false;
        if (!left &&  right) return false;

        if (left->val != right->val) return false;

        if (!isSymmetric(left->left,  right->right)) return false;
        if (!isSymmetric(left->right, right->left )) return false;

        return true;
    }
};

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

        stack<TreeNode *> leftStack, rightStack;
        leftStack.push(root->left);
        rightStack.push(root->right);

        while (!leftStack.empty()) {
            TreeNode *left = leftStack.top(),   *right = rightStack.top();
            leftStack.pop();                    rightStack.pop();

            if (!left && !right) continue;
            if (!left &&  right) return false;
            if ( left && !right) return false;
            if (left->val != right->val) return false;

            leftStack.push(left->left );        rightStack.push(right->right);
            leftStack.push(left->right);        rightStack.push(right->left);
        }


        return true;
    }
};