[LeetCode] 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.

» Solve this problem

[解题思路]
非递归解法：按层遍历，每一层检查一下是否对称。

递归解法：

其中左子树和右子树对称的条件：

1. 两个节点值相等，或者都为空
2. 左节点的左子树和右节点的右子树对称
3. 左节点的右子树和右节点的左子树对称

[Code]
非递归解法

1:  bool isSymmetric(TreeNode *root) {  
2:       if(root == NULL) return true;  
3:       vector<TreeNode*> visitQueue;  
4:       visitQueue.push_back(root);  
5:       int curLevel=1;            
6:       while(curLevel >0)  
7:       {  
8:            int i=0;  
9:            while(i<curLevel)  
10:            {  
11:                 TreeNode* p = visitQueue[i];  
12:                 i++;  
13:                 if(p==NULL) continue;  
14:                 visitQueue.push_back(p->left);  
15:                 visitQueue.push_back(p->right);  
16:            }  
17:            int start = 0, end = curLevel-1;  
18:            while(start< end)   
19:            {   
20:                 TreeNode *pl = visitQueue[start];   
21:                 TreeNode *pr = visitQueue[end];   
22:                 int l = pl== NULL? -1:pl->val;   
23:                 int r = pr== NULL? -1: pr->val;   
24:                 if(l!=r)   
25:                      return false;   
26:                 start++;   
27:                 end--;   
28:            }   
29:            visitQueue.erase(visitQueue.begin(), visitQueue.begin() + curLevel);                 
30:            curLevel = visitQueue.size();   
31:       }   
32:       return true;   
33:  }  

递归解法

1:    bool isSymmetric(TreeNode *root) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      if(root == NULL) return true;  
5:      return isSym(root->left, root->right);  
6:    }  
7:    bool isSym(TreeNode *left, TreeNode *right)  
8:    {  
9:      if(left == NULL)  
10:        return right ==NULL;  
11:      if(right == NULL)  
12:        return left == NULL;  
13:      if(left->val != right->val)  
14:        return false;  
15:      if(!isSym(left->left, right->right))  
16:        return false;  
17:      if(!isSym(left->right, right->left))  
18:        return false;  
19:      return true;  
20:    }