// 面试题27：二叉树的镜像

// 题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。

#include <iostream>

#include "BinaryTree.h"

#include <stack>

void MirrorRecursively(BinaryTreeNode *pNode)//递归算法（自下而上）

{

    if ((pNode == nullptr) || (pNode->m_pLeft == nullptr && pNode->m_pRight == nullptr))//鲁棒性

        return;

    BinaryTreeNode *pTemp = pNode->m_pLeft;//交换

    pNode->m_pLeft = pNode->m_pRight;

    pNode->m_pRight = pTemp;

    if (pNode->m_pLeft)//遍历

        MirrorRecursively(pNode->m_pLeft);

    if (pNode->m_pRight)

        MirrorRecursively(pNode->m_pRight);

}

void MirrorIteratively(BinaryTreeNode* pRoot)//迭代算法（自上而下）

{

    if (pRoot == nullptr)

        return;

    std::stack<BinaryTreeNode*> stackTreeNode;//建立一个栈

    stackTreeNode.push(pRoot);//压入根节点

    while (stackTreeNode.size() > )//当栈内有元素时

    {

        BinaryTreeNode *pNode = stackTreeNode.top();//取出栈顶元素

        stackTreeNode.pop();

        BinaryTreeNode *pTemp = pNode->m_pLeft;//交换该元素（即节点）的孩子

        pNode->m_pLeft = pNode->m_pRight;

        pNode->m_pRight = pTemp;

        if (pNode->m_pLeft)//如果节点孩子存在，把孩子压入堆栈

            stackTreeNode.push(pNode->m_pLeft);

        if (pNode->m_pRight)

            stackTreeNode.push(pNode->m_pRight);

    }

}

// ====================测试代码====================

// 测试完全二叉树：除了叶子节点，其他节点都有两个子节点

//            8

//        6      10

//       5 7    9  11

void Test1()

{

    printf("=====Test1 starts:=====\n");

    BinaryTreeNode* pNode8 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode6 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode10 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode7 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode9 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode11 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNode8, pNode6, pNode10);

    ConnectTreeNodes(pNode6, pNode5, pNode7);

    ConnectTreeNodes(pNode10, pNode9, pNode11);

    PrintTree(pNode8);

    printf("=====Test1: MirrorRecursively=====\n");

    MirrorRecursively(pNode8);

    PrintTree(pNode8);

    printf("=====Test1: MirrorIteratively=====\n");

    MirrorIteratively(pNode8);

    PrintTree(pNode8);

    DestroyTree(pNode8);

}

// 测试二叉树：出叶子结点之外，左右的结点都有且只有一个左子结点

//            8

//          7

//        6

//      5

//

void Test2()

{

    printf("=====Test2 starts:=====\n");

    BinaryTreeNode* pNode8 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode7 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode6 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode4 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNode8, pNode7, nullptr);

    ConnectTreeNodes(pNode7, pNode6, nullptr);

    ConnectTreeNodes(pNode6, pNode5, nullptr);

    ConnectTreeNodes(pNode5, pNode4, nullptr);

    PrintTree(pNode8);

    printf("=====Test2: MirrorRecursively=====\n");

    MirrorRecursively(pNode8);

    PrintTree(pNode8);

    printf("=====Test2: MirrorIteratively=====\n");

    MirrorIteratively(pNode8);

    PrintTree(pNode8);

    DestroyTree(pNode8);

}

// 测试二叉树：出叶子结点之外，左右的结点都有且只有一个右子结点

//            8

//             7

//              6

//               5

//                4

void Test3()

{

    printf("=====Test3 starts:=====\n");

    BinaryTreeNode* pNode8 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode7 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode6 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode4 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNode8, nullptr, pNode7);

    ConnectTreeNodes(pNode7, nullptr, pNode6);

    ConnectTreeNodes(pNode6, nullptr, pNode5);

    ConnectTreeNodes(pNode5, nullptr, pNode4);

    PrintTree(pNode8);

    printf("=====Test3: MirrorRecursively=====\n");

    MirrorRecursively(pNode8);

    PrintTree(pNode8);

    printf("=====Test3: MirrorIteratively=====\n");

    MirrorIteratively(pNode8);

    PrintTree(pNode8);

    DestroyTree(pNode8);

}

// 测试空二叉树：根结点为空指针

void Test4()

{

    printf("=====Test4 starts:=====\n");

    BinaryTreeNode* pNode = nullptr;

    PrintTree(pNode);

    printf("=====Test4: MirrorRecursively=====\n");

    MirrorRecursively(pNode);

    PrintTree(pNode);

    printf("=====Test4: MirrorIteratively=====\n");

    MirrorIteratively(pNode);

    PrintTree(pNode);

}

// 测试只有一个结点的二叉树

void Test5()

{

    printf("=====Test5 starts:=====\n");

    BinaryTreeNode* pNode8 = CreateBinaryTreeNode();

    PrintTree(pNode8);

    printf("=====Test4: MirrorRecursively=====\n");

    MirrorRecursively(pNode8);

    PrintTree(pNode8);

    printf("=====Test4: MirrorIteratively=====\n");

    MirrorIteratively(pNode8);

    PrintTree(pNode8);

}

int main(int argc, char* argv[])

{

    Test1();

    Test2();

    Test3();

    Test4();

    Test5();

    system("pause");

    return ;

}