首页 > 代码库 > HappyLeetcode43:Symmetric Tree
HappyLeetcode43: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
这道题目可以用迭代的方式做,也可以用递归的方式做。遇见和树相关的题目,第一反应是递归,所以我的解法是递归。
代码奉上:
class Solution { public: bool IsSymmetric(TreeNode *node1, TreeNode *node2) { if (node1 == NULL&&node2 == NULL) return true; if (node1 == NULL||node2 == NULL) return false; bool result1, result2; if (node1->val != node2->val) return false; else { result1 = IsSymmetric(node1->left, node2->right); result2 = IsSymmetric(node1->right, node2->left); } return result1&&result2; } bool isSymmetric(TreeNode *root) { if (root == NULL || root->left == NULL&&root->right == NULL) return true; bool result = IsSymmetric(root->left, root->right); return result; } };
看了相关人的解法,有的人直接用迭代的方式解出来了,感觉很受启发
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: bool isSymmetric(TreeNode *root) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. if(root == NULL)return true; queue<TreeNode*> qleft, qright; if(root->left)qleft.push(root->left); if(root->right)qright.push(root->right); while(qleft.empty() == false && qright.empty() == false) { TreeNode *ql = qleft.front(); TreeNode *qr = qright.front(); qleft.pop(); qright.pop(); if(ql->val == qr->val) { if(ql->left && qr->right) { qleft.push(ql->left); qright.push(qr->right); } else if(ql->left || qr->right) return false; if(qr->left && ql->right) { qleft.push(qr->left); qright.push(ql->right); } else if(qr->left || ql->right) return false; } else return false; } if(qleft.empty() && qright.empty()) return true; else return false; }};
转自http://www.cnblogs.com/TenosDoIt/p/3440729.html
HappyLeetcode43:Symmetric Tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。