// 面试题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");

}