LeetCode: Symmetric Tree

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:

But the following is not:

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

地址：https://oj.leetcode.com/problems/symmetric-tree/

算法：写了一个非递归的算法。用BFS遍历，每到一层结束判断该层节点是否对称，其中对于空的节点用0X80000000表示。代码：

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     bool isSymmetric(TreeNode *root) {
13         if(!root)   return true;
14         queue<TreeNode *> que;
15         int num_push = 0;
16         int num_pop  = 0;
17         int last     = 1;
18         que.push(root);
19         ++num_push;
20         vector<int> temp;
21         while(!que.empty()){
22             TreeNode *node_pop = que.front();
23             if(node_pop){
24                 temp.push_back(node_pop->val);
25                 que.push(node_pop->left);
26                 ++num_push;
27                 que.push(node_pop->right);
28                 ++num_push;
29             }
30             else
31                 temp.push_back(0x80000000);
32             que.pop();
33             ++num_pop;
34             if(num_pop == last){
35                 int i = 0;
36                 while(i < temp.size()/2 && temp[i] == temp[temp.size()-i-1])    ++i;
37                 if(i < temp.size()/2)   return false;
38                 last = num_push;
39                 temp.clear();
40             }
41         }
42         return true;
43     }
44     
45 };