2019-03-05  319 views 评论

《剑指Offer》题目解析(6)

 标签:

题目1 二叉树的镜像

题目描述

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

题目解析

一定要考虑到两种特殊情况:

  • 二叉树为空
  • 二叉树的左子树为空且二叉树的右子树为空

设计代码的时候一定要考虑代码的鲁棒性。所以需要设计到两个if语句,如果不在这两种特殊情况里面,再去新建一个TreeNode,然后交换进行做镜像。

代码

题目2 顺时针打印矩阵

题目描述

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

题目解析

用左上和右下的坐标定位出一次要旋转打印的数据,一次旋转打印结束后,往对角分别前进和后退一个单位。

代码

题目3 包含min函数的栈

题目描述

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

题目解析

我们需要一个辅助堆栈来得到我们所需要数据,因为只有一个堆栈的话,我们没办法比较得出最小值。加入我们的数据压入顺序是3,4,2,1。那么可以这样:

步骤 操作 数据栈 辅助栈 最小值
1 压入3 3 3 3
2 压入4 3,4 3,3 3
3 压入2 3,4,2 3,3,2 2
4 压入1 3,4,2,1 3,3,2,1 1
5 弹出 3,4,2 3,3,2 2
6 弹出 3,4 3,3 3
7 压入0 3,4,0 3,3,0 0

代码

题目4 栈的压入、弹出序列

题目描述

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

题目解析

这个程序的代码思路跟我们手工做题的思路一样,所以也许不是复杂度最低的算法,它的思路是这样的:
1. 新建一个vector数组temp;
2. 然后将pushV的最头上的元素压入temp;
3. 判断该元素是否和popV中最上面的元素(即要被弹出的元素)是否相等,若不相等正则去执行第2步,直到找到相等的,然后temp里面的元素弹出;
4. 然后开始第2个元素的比较,步骤重复2和3,直到所有的完成。

代码

题目5 从上往下打印二叉树

题目描述

从上往下打印出二叉树的每个结点,同层结点从左至右打印。

题目解析

这就是层序遍历。用层序遍历的法子,借助队列来实现。其实广度优先搜索也借鉴了层序遍历的思想。

代码

给我留言

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