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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Hide Tags

Tree Depth-first Search

　　这个嘛，用两个队列，一个维护树从左到右，一个维护树的从右到左。这就好了。写了两个，一个识queue 中是已经已经符合的，弹出后判断其子节点是否符合，这样queue 中不维护NULL。

 1 class Solution {
 2 public:
 3     bool isSymmetric(TreeNode *root) {
 4         if(root==NULL||(root->left==NULL&&root->right==NULL))  return true;
 5         if(root->left==NULL||root->right==NULL||root->left->val!=root->right->val)   return false;
 6         queue<TreeNode*> lft;
 7         lft.push(root->left);
 8         queue<TreeNode*> rgt;
 9         rgt.push(root->right);
10         while(( !lft.empty() )||( !rgt.empty() )){
11             int nlft=lft.size(),nrgt=rgt.size();
12             if(nlft!=nrgt)  return false;
13             for(int i=0;i<nlft;i++){
14                 TreeNode* curlft=lft.front(),*currgt=rgt.front();
15                 if( (curlft->left==NULL&&currgt->right!=NULL) ||
16                     (curlft->right==NULL&&currgt->left!=NULL) ) return false;
17                 if(curlft->left!=NULL&&
18                    currgt->right!=NULL&&
19                    curlft->left->val!=currgt->right->val)   return false;
20                 if(curlft->right!=NULL&&
21                    currgt->left!=NULL&&
22                    curlft->right->val!=currgt->left->val)   return false;
23                 if(curlft->left!=NULL)  lft.push(curlft->left);
24                 if(curlft->right!=NULL) lft.push(curlft->right);
25                 if(currgt->right!=NULL) rgt.push(currgt->right);
26                 if(currgt->left!=NULL)  rgt.push(currgt->left);
27                 lft.pop();
28                 rgt.pop();
29             }
30         }
31         return true;
32     }
33 };

View Code

　　一个是queue 中维护未判断的，包括NULL，这样写逻辑比较简单。

 1 #include <iostream>
 2 #include <queue>
 3 using namespace std;
 4 /**
 5  * Definition for binary tree
 6  */
 7 struct TreeNode {
 8     int val;
 9     TreeNode *left;
10     TreeNode *right;
11     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
12 };
13 /**
14 class Solution {
15 public:
16     bool isSymmetric(TreeNode *root) {
17         if(root==NULL||(root->left==NULL&&root->right==NULL))  return true;
18         if(root->left==NULL||root->right==NULL||root->left->val!=root->right->val)   return false;
19         queue<TreeNode*> lft;
20         lft.push(root->left);
21         queue<TreeNode*> rgt;
22         rgt.push(root->right);
23         while(( !lft.empty() )||( !rgt.empty() )){
24             int nlft=lft.size(),nrgt=rgt.size();
25             if(nlft!=nrgt)  return false;
26             for(int i=0;i<nlft;i++){
27                 TreeNode* curlft=lft.front(),*currgt=rgt.front();
28                 if( (curlft->left==NULL&&currgt->right!=NULL) ||
29                     (curlft->right==NULL&&currgt->left!=NULL) ) return false;
30                 if(curlft->left!=NULL&&
31                    currgt->right!=NULL&&
32                    curlft->left->val!=currgt->right->val)   return false;
33                 if(curlft->right!=NULL&&
34                    currgt->left!=NULL&&
35                    curlft->right->val!=currgt->left->val)   return false;
36                 if(curlft->left!=NULL)  lft.push(curlft->left);
37                 if(curlft->right!=NULL) lft.push(curlft->right);
38                 if(currgt->right!=NULL) rgt.push(currgt->right);
39                 if(currgt->left!=NULL)  rgt.push(currgt->left);
40                 lft.pop();
41                 rgt.pop();
42             }
43         }
44         return true;
45     }
46 };
47 */
48 
49 class Solution {
50 public:
51     bool isSymmetric(TreeNode *root) {
52         if(root==NULL)  return true;
53         queue<TreeNode* > lft,rgt;
54         lft.push(root->left);
55         rgt.push(root->right);
56         while((!lft.empty())||(!rgt.empty())){
57             TreeNode * curlft=lft.front(),*currgt=rgt.front();
58             lft.pop();
59             rgt.pop();
60             if(curlft==NULL&&currgt==NULL)  continue;
61             if(curlft==NULL||currgt==NULL||curlft->val!=currgt->val)  return false;
62             lft.push(curlft->left);
63             lft.push(curlft->right);
64             rgt.push(currgt->right);
65             rgt.push(currgt->left);
66         }
67         return true;
68     }
69 };
70 
71 int main()
72 {
73 
74     return 0;
75 }

View Code