题目链接：Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1 
   / \ 
  2   2 
 / \ / \ 
3  4 4  3

But the following is not:

    1 
   / \ 
  2   2 
   \   \ 
   3    3

Note:

Bonus points if you could solve it both recursively and iteratively.

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

   1 
  / \ 
 2   3 
    / 
   4 
    \ 
     5

The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.

这道题的要求是判断一棵树是否是对称的。

采用递归的思路，类似Same Tree，只不过这里是判断对称。

两棵子树l和r对称，也就是l和r的节点数字相同，而且l的左子树和r的右子树对称 而且 l的右子树和r的左子树对称。

时间复杂度：O(n)

空间复杂度：O(1)

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

class Solution
{
public:
    bool isSymmetric(TreeNode *root)
    {
        if(root == NULL)
            return true;
        return isSymmetric(root -> left, root -> right);
    }
private:
    bool isSymmetric(TreeNode *l, TreeNode *r)
    {
        if(l != NULL && r != NULL)
            return l -> val == r -> val 
                && isSymmetric(l -> left, r -> right) 
                && isSymmetric(l -> right, r -> left);
        else
            return l == NULL && r == NULL;
    }
};

至于迭代的方法，未完待续。。。