题目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压入3333
2压入43,43,33
3压入23,4,23,3,22
4压入13,4,2,13,3,2,11
5弹出3,4,23,3,22
6弹出3,43,33
7压入03,4,03,3,00

代码

题目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 从上往下打印二叉树

题目描述

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

题目解析

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

代码