剑指offer27.镜像二叉树

剑指offer27.镜像二叉树 题目描述

C++实现

```cpp
/* 二叉树镜像
*题目：完成一个函数，输入一个二叉树，输出该二叉树的镜像*/

#include
#include
#include
using namespace std;

struct TreeNode
{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

//递归实现
TreeNode* mirrorTree(TreeNode* root) {
    if (root == nullptr)
        return root;
    //叶子节点
    if (root->left == nullptr && root->right == nullptr)
    {
        return root;
    }
    //下面是交换两个子树
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    //对结点的左右子树进行处理
    if (root->left)  mirrorTree(root->left);
    if (root->right)  mirrorTree(root->right);
    return root;
}
//广度遍历
TreeNode * mirrorTreestack(TreeNode* root)
{
    //为空结点
    if (root == nullptr)
        return root;
    //建立栈进行存储
    stack<TreeNode*>stacktree;
    stacktree.push(root);
    while (!stacktree.empty())
    {
        TreeNode* top = stacktree.top();
        stacktree.pop();

        TreeNode* temp = top->left;
        top->left = top->right;
        top->right = temp;

        if (top->left)
            stacktree.push(top->left);
        if (top->right)
            stacktree.push(top->right);
    }
    return root;
}
//打印二叉树
static void printTree(TreeNode* node)
{
    if (node != nullptr)
    {
        
        printTree(node->left);
        cout << node->val << " ";
        printTree(node->right);
    }
}
//测试代码 
/* 完全二叉树：出来叶子节点，其他节点都有两个子节点
 *          8
 *       /     \
       6       10 
      / \      /  \
      5  7     9   11 
  */
void test1()
{
    cout << "测试完全二叉树" << endl;
    TreeNode* root = new TreeNode(8);
    root->left = new TreeNode(6);
    root->right= new TreeNode(10);
    root->left->left = new TreeNode(5);
    root->left->right = new TreeNode(7);
    root->right->left = new TreeNode(9);
    root->right->right = new TreeNode(11);
    printTree(root);
    cout << endl;
    TreeNode* node = mirrorTree(root);
    printTree(node);
}
void test2()
{
    cout << "测试完全二叉树" << endl;
    TreeNode* root = new TreeNode(8);
    root->left = new TreeNode(6);
    root->right = new TreeNode(10);
    root->left->left = new TreeNode(5);
    root->left->right = new TreeNode(7);
    root->right->left = new TreeNode(9);
    root->right->right = new TreeNode(11);
    printTree(root);
    cout << endl;
    TreeNode* node = mirrorTreestack(root);
    printTree(node);
}
int main()
{
    test1();
    cout << endl;
    test2();
    return 0;
}

`