題目描述
請實現(xiàn)一個函數(shù)，用來判斷一顆二叉樹是不是對稱的。注意硅堆，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的犁苏。
解題思路：
遞歸思想實現(xiàn)硬萍，首先分兩種情況進行考慮：
- 樹為空，直接返回true围详；
- 樹不為空朴乖，則轉(zhuǎn)去判斷左子樹和右子樹是否對稱，分以下兩種情況進行討論：
a. 左子樹和右子樹都為空助赞，直接返回true买羞；
b. 左子樹和右子樹都不為空，并且左子樹和右子樹根節(jié)點的值相等雹食，遞歸判斷左子樹的左子樹和右子樹的右子樹是否對稱畜普，以及左子樹的右子樹和右子樹的左子樹是否對稱，返回二者與的結(jié)果群叶；
c. 以上兩種情況不滿足時吃挑，直接返回false。
代碼實現(xiàn)：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
if(pRoot==NULL){
return true;
}
return equalLR(pRoot->left,pRoot->right);
}
bool equalLR(TreeNode* l,TreeNode* r){
if(l==NULL && r==NULL)
return true;
if(l && r){
if(l->val!=r->val){
return false;
}
else{
return equalLR(l->left,r->right) && equalLR(l->right,r->left);
}
}
return false;
}
};
非遞歸實現(xiàn)：
- 使用兩個棧輔助
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
if(pRoot==NULL){
return true;
}
if(!pRoot->left && !pRoot->right){
return true;
}
if(pRoot->left && pRoot->right){
stack<TreeNode*> l,r;
l.push(pRoot->left);
r.push(pRoot->right);
while(!l.empty() && !r.empty()){
TreeNode* lc=l.top();
l.pop();
TreeNode* rc=r.top();
r.pop();
if(lc->val != rc->val){
return false;
}
if(lc->left && rc->right){
l.push(lc->left);
r.push(rc->right);
}
else if(lc->left || rc->right)
return false;
if(lc->right && rc->left){
l.push(lc->right);
r.push(rc->left);
}
else if(lc->right || rc->left)
return false;
}
if(l.empty() && r.empty()){
return true;
}
return false;
}
return false;
}
};
- 使用一個棧輔助實現(xiàn)
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
if(pRoot==NULL){
return true;
}
stack<TreeNode*> v;
v.push(pRoot->left);
v.push(pRoot->right);
while(!v.empty()){
TreeNode* lc=v.top();
v.pop();
TreeNode* rc=v.top();
v.pop();
if(lc==NULL && rc==NULL)
continue;
if(lc==NULL || rc==NULL)
return false;
if(lc->val!=rc->val)
return false;
v.push(lc->left);
v.push(rc->right);
v.push(lc->right);
v.push(rc->left);
}
return true;
}
};
