leetcode 对称二叉树

非递归：层序遍历，然后为NULL叶节点填一个不可能的值用来判断；

 1 /**
 2  * Definition for a binary tree node.
 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==NULL) return true;
14         queue<TreeNode*> q;
15         q.push(root);
16         while(!q.empty()){
17             vector<int> ivec;
18             int len=q.size();
19             for(int i=0;i<len;i++){
20                 TreeNode* front=q.front();
21                 q.pop();
22                 if(front->left){
23                     q.push(front->left);
24                     ivec.push_back(front->left->val);
25                 }else{
26                     ivec.push_back(-1000000);
27                 }
28                 if(front->right){
29                     q.push(front->right);
30                     ivec.push_back(front->right->val);
31                 }else{
32                     ivec.push_back(-1000000);
33                 }
34             }
35             for(int i=0;i<ivec.size()-1-i;i++){
36                 int j=ivec.size()-1-i;
37                 if(ivec[i]!=ivec[j]){
38                     return false;
39                 }
40             }
41         }
42         return true;
43     }
44 };

递归方法：使用递归中序遍历，对NULL叶节点填充不可能数值，后进行对称判断；

 1 /**
 2  * Definition for a binary tree node.
 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==NULL) return true;
14         vector<int> ivec;
15         dfs(root,ivec);
16         for(int i=0;i<ivec.size()-1-i;i++){
17             int j=ivec.size()-1-i;
18             if(ivec[i]!=ivec[j]) return false;
19         }
20         return true;
21     }
22     void dfs(TreeNode* root,vector<int>& ivec){
23         if(root==NULL) return;
24         dfs(root->left,ivec);
25         if(root->left) 
26             ivec.push_back(root->left->val);
27         else
28             ivec.push_back(-1000000);
29         if(root->right)
30             ivec.push_back(root->right->val);
31         else
32             ivec.push_back(-1000000);
33         dfs(root->right,ivec);
34     }
35 };