首页 > 其他 > 详细

剑指offer-二叉树的镜像

时间:2019-02-24 10:27:47      阅读:166      评论:0      收藏:0      [点我收藏+]

二叉树的镜像

一、问题描述

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

二、算法思路

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

  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;
        }
    }
};

剑指offer-二叉树的镜像

原文:https://www.cnblogs.com/MarkKobs-blog/p/10425329.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!