剑指offer-二叉树的镜像

二叉树的镜像

一、问题描述

操作给定的二叉树,将其变换为源二叉树的镜像。

二、算法思路

这道题可以用递归的思想,将问题分解成同质的子问题,可以看到,根节点的子树需要先完成镜像翻转,然后再将根节点的两个孩子进行调换。

  1. 判断根节点是否是空,如果根节点为空,那么它也就没有孩子了,没有孩子就不必进行镜像翻转。
  2. 如果不空,那就将它的两个已经镜像翻转好的左右子树进行对调。

三、算法实现

3.1、C++实现版

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if(pRoot==NULL){return;//do nothing}
        else{
            //left child rotate
            Mirror(pRoot->left);
            //right child rotate
            Mirror(pRoot->right);
            
            //left to right,right to left
            TreeNode *temp=pRoot->left;
            pRoot->left=pRoot->right;
            pRoot->right=temp;
        }
    }
};
上一篇:java 常见连接池性能测试


下一篇:【剑指】二叉树的深度