EEPW论坛

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.

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

1. class Solution {  

2. public:  

3.     bool isSymmetirc(TreeNode* root)  

4.     {  

5.         if (root == NULL)  

6.         {  

7.             return true;  

8.         }  

9.   

10.         return check(root->left, root->right);  

11.     }  

12.   

13.     bool check(TreeNode* leftNode, TreeNode* rightNode)  

14.     {  

15.         if (leftNode==NULL && rightNode==NULL)  

16.         {  

17.             return true;  

18.         }  

19.   

20.         if ((leftNode!=NULL && rightNode==NULL)  

21.             || (leftNode==NULL && rightNode!=NULL))  

22.         {  

23.             return false;  

24.         }  

25.           

26.         if (leftNode->val!=rightNode->val)  

27.         {  

28.             return false;  

29.         }  

30.   

31.         return check(leftNode->left, rightNode->right) && check(leftNode->right, rightNode->left);  

32.     }  

33. };