二叉树的镜像

Love The Way You Lie 2023-03-14 13:14 32阅读 0赞

## 一、前言 ##

《剑指Offer》中题27

## 二、题目 ##

请完成一个函数，输入一棵二叉树，该函数输出它的镜像。叉树节点的定义如下：

![20200517230344591.png][]

## 三、思路 ##

递归实现即可

## 四、扩展 ##

测试用例中需要判断两颗二叉树是否互为镜像。有三种方法：

方法一，将其中一颗二叉树转为镜像，并与另外一棵树进行比较判断各节点值是否相等

方法二，互为镜像的两个二叉树，每层数据顺序相反，逐层判断即可，需要注意结点为空的情况。前面文章中《从上往下打印二叉树》给出了获得逐层获得树数据方法。

方法三：递归实现——树1左结点和树2右结点判断；树1右结点和树2左结点判断。

详细介绍见[《二叉树镜像判断》][Link 1]

《二叉树镜像判断》 [https://blog.csdn.net/nie2314550441/article/details/106189949][Link 1]

## 五、编码实现 ##

//==========================================================================
    /**
    * @file : MirrorOfBinaryTree.h
    * @purpose : 输入一棵二叉树，该函数输出它的镜像。
    *
    */
     //==========================================================================
    
    #pragma once
    #include "Common.h"
    #include "ConstructTree.h"
    #include "PrintTree.h"
    #include "GetTreesInLines.h"
    #include "MirrorOfBinaryTreeJudge.h"
    
    //输入两棵二叉树A和B，判断B是不是A的子结构。
    #define NAMESPACE_MIRROROFBINARYTREE namespace NAME_MIRROROFBINARYTREE {
    #define NAMESPACE_MIRROROFBINARYTREEEND }
    
    template<class T>
    void MirrorOfBinaryTree(BinaryTreeNode<T>* pRoot)
    {
        if (pRoot == nullptr)
        {
            return;
        }
    
        if (pRoot->m_pLeft == nullptr && pRoot->m_pRight == nullptr)
        {
            return;
        }
    
        BinaryTreeNode<T>* pTemp = pRoot->m_pLeft;
        pRoot->m_pLeft = pRoot->m_pRight;
        pRoot->m_pRight = pTemp;
    
        if (pRoot->m_pLeft)
        {
            MirrorOfBinaryTree(pRoot->m_pLeft);
        }
    
        if (pRoot->m_pRight)
        {
            MirrorOfBinaryTree(pRoot->m_pRight);
        }
    }
    
    //
    // 测试 用例 START
    NAMESPACE_MIRROROFBINARYTREE
    
    template<class T>
    void test(const char* testName, BinaryTreeNode<T>* pRoot, BinaryTreeNode<T>* pRootMirror, T empty)
    {
        cout << "--------------- " << testName << " start ---------------" << endl;
        map<int, vector<T>> srcData;    //记录的是每行节点值
        GetTreesInLines(pRoot, srcData, empty);
        cout << "打印 原二叉树结构如下(" << "空节点用" << empty << "代替)" << endl;
        PrintTree((int)srcData.size(), srcData);
    
        map<int, vector<T>> mirrorData; //记录的是每行节点值
        GetTreesInLines(pRootMirror, mirrorData, empty);
        cout << "打印 镜像二叉树结构如下(" << "空节点用" << empty << "代替)" << endl;
        PrintTree((int)mirrorData.size(), mirrorData);
    
        // 判断两个二叉树是否互为镜像
    	bool result_Solution1 = MirrorOfBinaryTreeJudge_Solution1(pRoot, pRootMirror); // 方法一
    	bool result_Solution2 = MirrorOfBinaryTreeJudge_Solution2(pRoot, pRootMirror); // 方法二
    	bool result_Solution3 = MirrorOfBinaryTreeJudge_Solution3(pRoot, pRootMirror); // 方法三
    
        // 验证结果
        if (result_Solution1) { cout << " Solution1，验证结果: passed." << endl; }
        else { cout << " Solution1，验证结果: failed." << endl; }
    
    	if (result_Solution2) { cout << " Solution2，验证结果: passed." << endl; }
    	else { cout << " Solution2，验证结果: failed." << endl; }
    
    	if (result_Solution3) { cout << " Solution3，验证结果: passed." << endl; }
    	else { cout << " Solution3，验证结果: failed." << endl; }
    
        cout << "--------------- " << testName << " endl ---------------\n" << endl;
    }
    
    // 完全二叉树
    //              8
    //           /     \
    //          6      10  
    //         / \     / \
    //        5   7   9   11
    void Test1()
    {
        const int length = 7;
        int preorder[length] = { 8,6,5,7,10,9,11 };
        int inorder[length] = { 5,6,7,8,9,10,11 };
        int empty = -1;
    
        BinaryTreeNode<int>* pRoot = ConstructTree(preorder, inorder, length);
        BinaryTreeNode<int>* pMirror = ConstructTree(preorder, inorder, length);
        MirrorOfBinaryTree(pMirror);
       
        test("Test1", pRoot, pMirror, empty);
    }
    
    // 普通二叉树
    //                a
    //            /       \
    //           b         c  
    //         /   \      / \
    //        d     e    f   g
    //             / \     
    //            h   i  
    void Test2()
    {
        const int length = 9;
        char preorder[length + 1] = "abdehicfg";
        char inorder[length + 1] = "dbheiafcg";
        char empty = ' ';
    
        BinaryTreeNode<char>* pRoot = ConstructTree(preorder, inorder, length);
        BinaryTreeNode<char>* pMirror = ConstructTree(preorder, inorder, length);
        MirrorOfBinaryTree(pMirror);
    
        test("Test2", pRoot, pMirror, empty);
    }
    
    // 所有结点都没有右子结点
    //            1
    //           / 
    //          2   
    //         / 
    //        3 
    //       /
    //      4
    //     /
    //    5
    void Test3()
    {
        const int length = 5;
        char preorder[length + 1] = "12345";
        char inorder[length + 1] = "54321";
        char empty = '-';
    
        BinaryTreeNode<char>* pRoot = ConstructTree(preorder, inorder, length);
        BinaryTreeNode<char>* pMirror = ConstructTree(preorder, inorder, length);
        MirrorOfBinaryTree(pMirror);
    
        test("Test3", pRoot, pMirror, empty);
    }
    
    // 所有结点都没有左子结点
    //            1
    //             \ 
    //              2   
    //               \ 
    //                3 
    //                 \
    //                  4
    //                   \
    //                    5
    void Test4()
    {
        const int length = 5;
        char preorder[length + 1] = "12345";
        char inorder[length + 1] = "12345";
        char empty = '-';
    
        BinaryTreeNode<char>* pRoot = ConstructTree(preorder, inorder, length);
        BinaryTreeNode<char>* pMirror = ConstructTree(preorder, inorder, length);
        MirrorOfBinaryTree(pMirror);
    
        test("Test4", pRoot, pMirror, empty);
    }
    
    NAMESPACE_MIRROROFBINARYTREEEND
    // 测试 用例 END
    //
    
    void MirrorOfBinaryTree_Test()
    {
        NAME_MIRROROFBINARYTREE::Test1();
        NAME_MIRROROFBINARYTREE::Test2();
        NAME_MIRROROFBINARYTREE::Test3();
        NAME_MIRROROFBINARYTREE::Test4();
    }

**执行结果：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

[20200517230344591.png]: /images/20230312/1a5295ef37534cb58b8f4dfe58b28311.png
[Link 1]: https://blog.csdn.net/nie2314550441/article/details/106189949
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: /images/20230312/da3f36913ab944be86c549e6f6e9a3da.png