剑指Offer(十八):二叉树的镜像

2017年12月9日10:06:54 6 3,081 °C
摘要

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

剑指Offer(十八):二叉树的镜像

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

如下图所示:

剑指Offer(十八):二叉树的镜像

1、思路

先交换根节点的两个子结点之后,我们注意到值为10、6的结点的子结点仍然保持不变,因此我们还需要交换这两个结点的左右子结点。做完这两次交换之后,我们已经遍历完所有的非叶结点。此时变换之后的树刚好就是原始树的镜像。交换示意图如下所示:

剑指Offer(十八):二叉树的镜像

2、代码

C++:

Python2.7:

weinxin
微信公众号
分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类文章,欢迎您的关注!
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:6   其中:访客  3   博主  3

    • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3

      python2.7
      请问输入输出是怎么样的呢?

        • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点

          @小小毛 什么意思?输入输出是什么样子的?

            • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3

              @Jack Cui 我想表达的意思是,定义的这个类的输入是什么?我没有看到测试例子。虽然牛客网显示运行成功,但是我并不知道,怎么举例(或者说,没有if __name__ == ‘__main__’:
              main())

                • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点

                  @小小毛 牛客网这种的题,你不用管怎么调用这个函数。函数的参数,就算输入了。

            • avatar EzJobSniper 来自天朝的朋友 谷歌浏览器 Windows 10 上海交通大学 电信学院大楼2号楼 0

              or (root.left == None and root.right == None)似乎没有必要?

                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                  @EzJobSniper 确实,逻辑上来讲,没有必要,早返回,晚返回的问题。