LEET code -- 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.





找對稱
去比對root底下

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isSymmetric(struct TreeNode* root) { if(root==NULL)return true; int ans=trace(root->left,root->right); return ans==-1? false:true; } int trace(struct TreeNode *leroot, struct TreeNode* riroot){ if(leroot==NULL && riroot==NULL)return 1; if(leroot==NULL && riroot)return -1; if(leroot && riroot==NULL)return -1; if(leroot->val!=riroot->val)return -1; int le = trace(leroot->left, riroot->right); int ri = trace(leroot->right,riroot->left); if(le==-1 || ri==-1 )return -1; else return 1; }

------
用LOOP

這邊寫死128  事實上應該要在while裡面用remalloc去動態新增

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isSymmetric(struct TreeNode* root) { if(root==NULL)return true; //int ans=trace(root->left,root->right); //return ans==-1? false:true; struct TreeNode** lestack=malloc(sizeof(struct TreeNode*)*128); struct TreeNode** ristack=malloc(sizeof(struct TreeNode*)*128); int lesize=0,risize=0; lestack[lesize++]=root->left; ristack[risize++]=root->right; while(lesize!=0 || risize!=0){ struct TreeNode *le=lestack[--lesize]; struct TreeNode *ri=ristack[--risize]; if(le==NULL && ri)return false; if(le && ri==NULL)return false; if(le==NULL && ri==NULL)continue; if(le->val != ri->val)return false; lestack[lesize++]=le->left; ristack[risize++]=ri->right; lestack[lesize++]=le->right; ristack[risize++]=ri->left; } return lesize==risize? true:false; }