??
Symmetric Tree Total Accepted:
61440 Total Submissions:
194643 My Submissions
?
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.
?
c++ 解决方案：
?
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#include
using namespace std;
typedef pair
nodepair; class Solution { public: bool isSymmetricRecursive(TreeNode*a,TreeNode*b){ if(a){ return b && a->val==b->val && isSymmetricRecursive(a->left,b->right) && isSymmetricRecursive(a->right,b->left); } return !b; } bool isSymmetricRecursive(TreeNode*root){ return !root || isSymmetricRecursive(root->left,root->right); } bool isSymmetric(TreeNode *root) { // Level-order BFS. queue
q; if(root) q.push(make_pair(root->left,root->right)); while(q.size()){ nodepair p=q.front(); q.pop(); if(p.first){ if(!p.second)return false; if(p.first->val != p.second->val) return false; // the order of children pushed to q is the key to the solution. q.push(make_pair(p.first->left,p.second->right)); q.push(make_pair(p.first->right,p.second->left)); } else if(p.second) return false; } return true; } };
?
?
第二种，非递归解决方案：
?
/**
* 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) {
TreeNode *left, *right;
if (!root)
return true;
queue
q1, q2;
q1.push(root->left);
q2.push(root->right);
while (!q1.empty() && !q2.empty()){
left = q1.front();
q1.pop();
right = q2.front();
q2.pop();
if (NULL == left && NULL == right)
continue;
if (NULL == left || NULL == right)
return false;
if (left->val != right->val)
return false;
q1.push(left->left);
q1.push(left->right);
q2.push(right->right);
q2.push(right->left);
}
return true;
}
};
?
?
?
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root) return true;
stack
sk;
sk.push(root->left);
sk.push(root->right);
TreeNode* pA, *pB;
while(!sk.empty()) {
pA = sk.top();
sk.pop();
pB = sk.top();
sk.pop();
if(!pA && !pB) continue;
if(!pA || !pB) return false;
if(pA->val != pB->val) return false;
sk.push(pA->left);
sk.push(pB->right);
sk.push(pA->right);
sk.push(pB->left);
}
return true;
}
};
?
c版本：
?
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool checkNodes(struct TreeNode* a, struct TreeNode* b)
{
if(a == NULL && b == NULL)
{
return true;
}
if(a == NULL || b == NULL)
{
return false;
}
if(a->val != b->val)
{
return false;
}
return checkNodes(a->left, b->right) && checkNodes(a->right, b->left);
}
bo