I recall reading in “Programming Pearls” that you should first have an idea – an “aha!” moment of inspiration – then find a suitable data structure, and finally write the code. That’s my understanding of the process.
As for this problem, well… ever since I learned about binary tree serialization, I’ve been using it everywhere. But here it kept giving me WA – 188 out of 190 test cases passed.
Frustrating.
After struggling for a day, I couldn’t resist and looked at other people’s approaches. So little code! Painful.
It’s actually just recursion. The key insight during recursion is to mirror: compare the left child’s left subtree with the right child’s right subtree, and vice versa.
Code below. After changing the approach, AC on the first try.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(root == NULL)
            return true;
        return CheckEqual(root->left,root->right);
    }
    bool CheckEqual(TreeNode * left,TreeNode * right)
    {
        if(left == NULL && right == NULL)
            return true;
        if((left == NULL && right != NULL)||(left != NULL && right == NULL))
            return false;
        if(left->val != right->val)
            return false;
        return CheckEqual(left->left,right->right)&&CheckEqual(left->right,right->left);
    }
};