《剑指offer》第二十八题(对称的二叉树)

// 面试题28:对称的二叉树
// 题目:请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和
// 它的镜像一样,那么它是对称的。 #include <iostream>
#include "BinaryTree.h" 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)//当二者都为空,true
return true; if (pRoot1 == nullptr || pRoot2 == nullptr)//只有一个为空,flase
return false; if (pRoot1->m_nValue != pRoot2->m_nValue)//当二者值不等,flase
return false; return isSymmetrical(pRoot1->m_pLeft, pRoot2->m_pRight)
&& isSymmetrical(pRoot1->m_pRight, pRoot2->m_pLeft);//看看你镜像和我是不是一样~
}//注意这里有个关键是,要测试是否都是空的,详见test9和10 // ====================测试代码====================
void Test(const char* testName, BinaryTreeNode* pRoot, bool expected)
{
if (testName != nullptr)
printf("%s begins: ", testName); if (isSymmetrical(pRoot) == expected)
printf("Passed.\n");
else
printf("FAILED.\n");
} // 8
// 6 6
// 5 7 7 5
void Test1()
{
BinaryTreeNode* pNode8 = CreateBinaryTreeNode();
BinaryTreeNode* pNode61 = CreateBinaryTreeNode();
BinaryTreeNode* pNode62 = CreateBinaryTreeNode();
BinaryTreeNode* pNode51 = CreateBinaryTreeNode();
BinaryTreeNode* pNode71 = CreateBinaryTreeNode();
BinaryTreeNode* pNode72 = CreateBinaryTreeNode();
BinaryTreeNode* pNode52 = CreateBinaryTreeNode(); ConnectTreeNodes(pNode8, pNode61, pNode62);
ConnectTreeNodes(pNode61, pNode51, pNode71);
ConnectTreeNodes(pNode62, pNode72, pNode52); Test("Test1", pNode8, true); DestroyTree(pNode8);
} // 8
// 6 9
// 5 7 7 5
void Test2()
{
BinaryTreeNode* pNode8 = CreateBinaryTreeNode();
BinaryTreeNode* pNode61 = CreateBinaryTreeNode();
BinaryTreeNode* pNode9 = CreateBinaryTreeNode();
BinaryTreeNode* pNode51 = CreateBinaryTreeNode();
BinaryTreeNode* pNode71 = CreateBinaryTreeNode();
BinaryTreeNode* pNode72 = CreateBinaryTreeNode();
BinaryTreeNode* pNode52 = CreateBinaryTreeNode(); ConnectTreeNodes(pNode8, pNode61, pNode9);
ConnectTreeNodes(pNode61, pNode51, pNode71);
ConnectTreeNodes(pNode9, pNode72, pNode52); Test("Test2", pNode8, false); DestroyTree(pNode8);
} // 8
// 6 6
// 5 7 7
void Test3()
{
BinaryTreeNode* pNode8 = CreateBinaryTreeNode();
BinaryTreeNode* pNode61 = CreateBinaryTreeNode();
BinaryTreeNode* pNode62 = CreateBinaryTreeNode();
BinaryTreeNode* pNode51 = CreateBinaryTreeNode();
BinaryTreeNode* pNode71 = CreateBinaryTreeNode();
BinaryTreeNode* pNode72 = CreateBinaryTreeNode(); ConnectTreeNodes(pNode8, pNode61, pNode62);
ConnectTreeNodes(pNode61, pNode51, pNode71);
ConnectTreeNodes(pNode62, pNode72, nullptr); Test("Test3", pNode8, false); DestroyTree(pNode8);
} // 5
// / \
// 3 3
// / \
// 4 4
// / \
// 2 2
// / \
// 1 1
void Test4()
{
BinaryTreeNode* pNode5 = CreateBinaryTreeNode();
BinaryTreeNode* pNode31 = CreateBinaryTreeNode();
BinaryTreeNode* pNode32 = CreateBinaryTreeNode();
BinaryTreeNode* pNode41 = CreateBinaryTreeNode();
BinaryTreeNode* pNode42 = CreateBinaryTreeNode();
BinaryTreeNode* pNode21 = CreateBinaryTreeNode();
BinaryTreeNode* pNode22 = CreateBinaryTreeNode();
BinaryTreeNode* pNode11 = CreateBinaryTreeNode();
BinaryTreeNode* pNode12 = CreateBinaryTreeNode(); ConnectTreeNodes(pNode5, pNode31, pNode32);
ConnectTreeNodes(pNode31, pNode41, nullptr);
ConnectTreeNodes(pNode32, nullptr, pNode42);
ConnectTreeNodes(pNode41, pNode21, nullptr);
ConnectTreeNodes(pNode42, nullptr, pNode22);
ConnectTreeNodes(pNode21, pNode11, nullptr);
ConnectTreeNodes(pNode22, nullptr, pNode12); Test("Test4", pNode5, true); DestroyTree(pNode5);
} // 5
// / \
// 3 3
// / \
// 4 4
// / \
// 6 2
// / \
// 1 1
void Test5()
{
BinaryTreeNode* pNode5 = CreateBinaryTreeNode();
BinaryTreeNode* pNode31 = CreateBinaryTreeNode();
BinaryTreeNode* pNode32 = CreateBinaryTreeNode();
BinaryTreeNode* pNode41 = CreateBinaryTreeNode();
BinaryTreeNode* pNode42 = CreateBinaryTreeNode();
BinaryTreeNode* pNode6 = CreateBinaryTreeNode();
BinaryTreeNode* pNode22 = CreateBinaryTreeNode();
BinaryTreeNode* pNode11 = CreateBinaryTreeNode();
BinaryTreeNode* pNode12 = CreateBinaryTreeNode(); ConnectTreeNodes(pNode5, pNode31, pNode32);
ConnectTreeNodes(pNode31, pNode41, nullptr);
ConnectTreeNodes(pNode32, nullptr, pNode42);
ConnectTreeNodes(pNode41, pNode6, nullptr);
ConnectTreeNodes(pNode42, nullptr, pNode22);
ConnectTreeNodes(pNode6, pNode11, nullptr);
ConnectTreeNodes(pNode22, nullptr, pNode12); Test("Test5", pNode5, false); DestroyTree(pNode5);
} // 5
// / \
// 3 3
// / \
// 4 4
// / \
// 2 2
// \
// 1
void Test6()
{
BinaryTreeNode* pNode5 = CreateBinaryTreeNode();
BinaryTreeNode* pNode31 = CreateBinaryTreeNode();
BinaryTreeNode* pNode32 = CreateBinaryTreeNode();
BinaryTreeNode* pNode41 = CreateBinaryTreeNode();
BinaryTreeNode* pNode42 = CreateBinaryTreeNode();
BinaryTreeNode* pNode21 = CreateBinaryTreeNode();
BinaryTreeNode* pNode22 = CreateBinaryTreeNode();
BinaryTreeNode* pNode12 = CreateBinaryTreeNode(); ConnectTreeNodes(pNode5, pNode31, pNode32);
ConnectTreeNodes(pNode31, pNode41, nullptr);
ConnectTreeNodes(pNode32, nullptr, pNode42);
ConnectTreeNodes(pNode41, pNode21, nullptr);
ConnectTreeNodes(pNode42, nullptr, pNode22);
ConnectTreeNodes(pNode21, nullptr, nullptr);
ConnectTreeNodes(pNode22, nullptr, pNode12); Test("Test6", pNode5, false); DestroyTree(pNode5);
} // 只有一个结点
void Test7()
{
BinaryTreeNode* pNode1 = CreateBinaryTreeNode();
Test("Test7", pNode1, true); DestroyTree(pNode1);
} // 没有结点
void Test8()
{
Test("Test8", nullptr, true);
} // 所有结点都有相同的值,树对称
// 5
// / \
// 5 5
// / \
// 5 5
// / \
// 5 5
void Test9()
{
BinaryTreeNode* pNode1 = CreateBinaryTreeNode();
BinaryTreeNode* pNode21 = CreateBinaryTreeNode();
BinaryTreeNode* pNode22 = CreateBinaryTreeNode();
BinaryTreeNode* pNode31 = CreateBinaryTreeNode();
BinaryTreeNode* pNode32 = CreateBinaryTreeNode();
BinaryTreeNode* pNode41 = CreateBinaryTreeNode();
BinaryTreeNode* pNode42 = CreateBinaryTreeNode(); ConnectTreeNodes(pNode1, pNode21, pNode22);
ConnectTreeNodes(pNode21, pNode31, nullptr);
ConnectTreeNodes(pNode22, nullptr, pNode32);
ConnectTreeNodes(pNode31, pNode41, nullptr);
ConnectTreeNodes(pNode32, nullptr, pNode42);
ConnectTreeNodes(pNode41, nullptr, nullptr);
ConnectTreeNodes(pNode42, nullptr, nullptr); Test("Test9", pNode1, true); DestroyTree(pNode1);
} // 所有结点都有相同的值,树不对称
// 5
// / \
// 5 5
// / \
// 5 5
// / /
// 5 5
void Test10()
{
BinaryTreeNode* pNode1 = CreateBinaryTreeNode();
BinaryTreeNode* pNode21 = CreateBinaryTreeNode();
BinaryTreeNode* pNode22 = CreateBinaryTreeNode();
BinaryTreeNode* pNode31 = CreateBinaryTreeNode();
BinaryTreeNode* pNode32 = CreateBinaryTreeNode();
BinaryTreeNode* pNode41 = CreateBinaryTreeNode();
BinaryTreeNode* pNode42 = CreateBinaryTreeNode(); ConnectTreeNodes(pNode1, pNode21, pNode22);
ConnectTreeNodes(pNode21, pNode31, nullptr);
ConnectTreeNodes(pNode22, nullptr, pNode32);
ConnectTreeNodes(pNode31, pNode41, nullptr);
ConnectTreeNodes(pNode32, pNode42, nullptr);
ConnectTreeNodes(pNode41, nullptr, nullptr);
ConnectTreeNodes(pNode42, nullptr, nullptr); Test("Test10", pNode1, false); DestroyTree(pNode1);
} void main(int argc, char* argv[])
{
Test1();
Test2();
Test3();
Test4();
Test5();
Test6();
Test7();
Test8();
Test9();
Test10();
system("pause");
}
上一篇:Good Bye 2015B(模拟或者二进制枚举)


下一篇:lecture14-RBM的堆叠、修改以及DBN的决策学习和微调