題目
請實現(xiàn)一個函數(shù),用來判斷一棵二叉樹是不是對稱的。如果一棵二叉樹和它的鏡像一樣穷绵,那么它是對稱的碴巾。例如,在如圖4.3所示的3棵二叉樹中配并,第一棵二叉樹是對稱的括荡,而另外兩棵不是
思路
- 思路一
使用遞歸實現(xiàn),根節(jié)點的左右子樹相同溉旋,左子樹的左子樹和右子樹的右子樹相同畸冲,左子樹的右子樹和右子樹的左子樹相同即可
- 思路二
使用非遞歸,采用椆劾埃或隊列存取各級子樹根節(jié)點
算法實現(xiàn)
定義二叉樹
#include <iostream>
using namespace std;
struct BinaryTreeNode {
int m_nValue;
BinaryTreeNode *m_pLeft;
BinaryTreeNode *m_pRight;
};
遞歸
bool isSymmetrical(BinaryTreeNode *pRoot1, BinaryTreeNode *pRoot2);
bool isSymmetrical(BinaryTreeNode *pRoot) {
return isSymmetrical(pRoot, pRoot);
}
bool isSymmetrical(BinaryTreeNode *pRoot1, BinaryTreeNode *pRoot2) {
if (pRoot1 == nullptr && pRoot2 == nullptr)
return true;
if (pRoot1 == nullptr || pRoot2 == nullptr)
return false;
if (pRoot1->m_nValue != pRoot2->m_nValue)
return false;
return isSymmetrical(pRoot1->m_pLeft, pRoot2->m_pRight) &&
isSymmetrical(pRoot1->m_pRight, pRoot2->m_pLeft);
}
非遞歸(棧)
bool isSymmetricalStack(BinaryTreeNode *pRoot)
{
if(pRoot == nullptr) return true;
// 使用單棧
stack<BinaryTreeNode *> stack;
// 入棧
stack.push(pRoot->m_pLeft);
stack.push(pRoot->m_pRight);
while(!stack.empty()) {
// 成對取出
BinaryTreeNode *rightNode = stack.top();
stack.pop();
BinaryTreeNode *leftNode = stack.top();
stack.pop();
// 若都為空邑闲,繼續(xù)
if(leftNode == nullptr && rightNode == nullptr) continue;
// 一個為空,返回false
if(leftNode == nullptr || rightNode == nullptr) return false;
// 不為空梧油,比較當(dāng)前值苫耸,值不等,返回false儡陨;
if(leftNode->m_nValue != rightNode->m_nValue) return false;
// 確定入棧順序褪子,每次入棧都是成對成對的
stack.push(leftNode->m_pLeft);
stack.push(rightNode->m_pRight);
stack.push(leftNode->m_pRight);
stack.push(rightNode->m_pLeft);
}
return true;
}
非遞歸(隊列)
bool isSymmetricalQueue(BinaryTreeNode *pRoot)
{
if(pRoot == nullptr) return true;
// 使用兩個隊列
queue<BinaryTreeNode *> queue1, queue2;
queue1.push(pRoot->m_pLeft);
queue2.push(pRoot->m_pRight);
BinaryTreeNode *leftNode, *rightNode;
while(!queue1.empty() && !queue2.empty()) {
// 成對取出
leftNode= queue1.front();
queue1.pop();
rightNode= queue2.front();
queue2.pop();
if(leftNode == nullptr && rightNode == nullptr) continue;
if(leftNode == nullptr || rightNode == nullptr) return false;
if(leftNode->m_nValue != rightNode->m_nValue) return false;
// 成對插入
queue1.push(leftNode->m_pLeft);
queue1.push(leftNode->m_pRight);
queue2.push(rightNode->m_pRight);
queue2.push(rightNode->m_pLeft);
}
return true;
}
參考
《劍指offer》
對稱二叉樹