## Monday, January 7, 2013

### [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:    }
``````