首页 > 代码库 > [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:
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.
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 };
一个是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 }
[LeetCode] Symmetric Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。