剑指offer笔记（四） 第26题至第32题

剑指offer笔记（四） 第26题至第32题

• 前言
• 
  

  一、JZ26 树的子结构

• 
  

  二、JZ27 二叉树的镜像

• 
  

  三、JZ28 对称的二叉树

• 
  

  四、JZ29 顺时针打印矩阵

• 
  

  五、JZ30 包含min函数的栈

• 
  

  六、JZ31 栈的压入、d出序列

• 
  

  七、JZ32 - 1 从上到下打印二叉树 I

• 
  

  八、JZ32 - 2 从上到下打印二叉树 II

• 九、JZ32 - 3 从上到下打印二叉树 III
• 十、总结

---

前言

这次主要记录剑指offer的9道题，主要使用的语言是python，下面将对这9道题的一些感悟和知识点进行汇总！

---

提示：以下是本篇文章正文内容，下面案例可供参考 截图来源于LeetCode

一、JZ26 树的子结构

  见树，用递归！可以考虑使用两个递归来解决这道题，首先呐，需要确定树A与树B都是存在的，之后，判断树A与树B是否相同；最后判断树B是树A的左子树，还是树A的右子树。

OK，两个递归，isSame(t1,t2) 用于判断t1与t2是否一样，isSubtructure(A,B) 用于判断树A的子结构是否与树B相同。

以下为程序源码：

二、JZ27 二叉树的镜像

  见树，用递归了！其中下面的这行代码很有特色，可以好好记住并使用。

	root.left,root.right = root.right,root.left

以下为程序源码

三、JZ28 对称的二叉树

  紧接上一道题哦！JZ27在交换左右子树的值，这道题便是判断树A的左子树是否为树B的右子树，具体的看代码，不过需要注意，把情况列举清楚了！如果树A与树B的左右子树都没有，默认是对称的，反之一个有一个没有，那就是False了。

以下为程序源码：

四、JZ29 顺时针打印矩阵

  中规中矩的判断路径情况即可，先向右走，走到什么位置，同理，向下，向左，向上，依次列举出。

以下为程序源码：

五、JZ30 包含min函数的栈

  因为要实现时间复杂度O(1)，所以只能牺牲空间换时间，使用辅助栈B存储A每一个位置上对应的最小值。

以下为程序源码：

六、JZ31 栈的压入、d出序列

  必须搞清楚，栈 - 先进后出，这里使用stack[-1]==popped[index]则是判断当前压入元素是否等于popped[index]的元素，如果是，那么stack.pop()，不是的话，继续stack.append()了。

以下为程序源码：

七、JZ32 - 1 从上到下打印二叉树 I

  没什么特别说明的，这里使用的层序遍历，使用的是迭代的方法，deque()双头队列是真的牛！popleft()从队列左面d出，pop()从队列右面d出，实在是好用啊！！！以后刷题会很多次遇到这个美丽的函数。

以下为程序源码：

八、JZ32 - 2 从上到下打印二叉树 II

  上一道题的扩展，需要记录遍历每层的结果作为res的子集tmp。

这道题是经典的BFS模板，非常值得背诵记忆！！！

以下为程序源码：

九、JZ32 - 3 从上到下打印二叉树 III

  加个标志符flag，用它的正负调控每次tmp的输出顺序即可！

以下为程序源码：

十、总结

  这9道题都很基础，前三道树、后三道都是树的简单题，中间有矩阵、栈、队列的一些题，总的来说还是需要好好的学习数据结构中的基础知识，并将其转化成python的具体代码记忆在脑中，以备不时之需。

最近，忽然觉着甚是焦虑不堪，我有些搞不明白，如果打算去做一件事情，而考虑的要素过于充分是不是一件好事情，现在看来，适当考虑一下就可以了，但必须符合自己的预期目标或者说基础的出发点，只要这个基本要素是符合的，那就大胆去干吧！什么也别多想，年轻人看好什么后就努力去学，去掌握，永远身怀一颗赤诚的向学之心去努力就成！
  最后，半个月没更了，这两天补上，继续背诗，学乐律，既然不知道以后做什么，喜欢什么，那就好好对待现在吧！