18. 二叉树的镜像 题目描述操作给定的二叉树，将其变换为源二叉树的镜像。 思路根据源二叉树镜像的定义，交换每个节点的左子树和右子树 代码实现 # -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # 返回镜像树的根节点 def Mirror(self, root): # write co...

17. 树的子结构 题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） 思路我们约定空树不是任意一个树的子结构，所以只有当A、B均不为空时才判断B树是否为A的子树、子结构。如果B是A的子结构，则B的根节点一定在A中出现，首先在A中找到B的根节点所在，然后判断A树中这个节点下是否出现B的结构。 python代码实现 # -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = N...

4. 重建二叉树 题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 思路前序遍历：根结点 ---> 左子树 ---> 右子树中序遍历：左子树---> 根结点 ---> 右子树后序遍历：左子树 ---> 右子树 ---> 根结点已知中序遍历和前序(或者后序)遍历可以确定一棵唯一的二叉树，已知前序遍历和后序遍历不能确定一棵唯一的二叉树。本题可用递归的思想，已知前序遍历...

56. 删除链表中重复的结点 题目描述在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5 思路在遍历的时候，记录上一个不重复的节点pPre，当前节点pThis，下个节点pNext。在遍历pThis的时候如果当前节点pThis的值跟后面的几个节点数值相同，需要找到下个不同的节点，删除重复节点，更新pPre和pThis；如果前节点pThis的值跟后面的节点数值不同，直接更新pPre和pThis。如果pHead就是重复的，需要更新...

55. 链表中环的入口结点 题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 思路链表有环的意思就是，最后一个节点的next指向了前面的某个节点，链表没有None的链表尾部出口。思路一：引入辅助空间，用一个列表保存已经遍历过的节点，如果再次出现，则说明这个节点就是链表环的入口节点。思路二：设：链表长度为N，链表环长度为m1.用两个指针来遍历这个链表，一个每次走一步，一个每次走两步，两个指针会在链表环中的节点相遇。2.然后继续遍历其中的一个，步长为1，可以计算出链表环中节点的个数m。3.重新遍历链表，一个指针从头结点0开始(距链表环入口节点N-m)，另一个节点...

36. 两个链表的第一个公共结点 题目描述输入两个链表，找出它们的第一个公共结点。 思路两个链表有交叉的部分，则交叉部分为公共节点，由于链表的每个节点只有唯一的一个next，所以，链表交叉后，之后的节点全部是公共节点，不会再有分叉了。思路一：将两个链表合并，形成pHead1+pHead2和pHead2+pHead1两个链表，这两个链表长度相等，后面的几个节点必定是相同的公共节点，分别对两个链表进行遍历，并比较当前节点，如果相等则说明这个是公共节点，返回即可得第一个公共节点。思路二：还有一种思路是获取链表的长度，将长的链表长出来的部分删(遍历)掉，然后再跟短链表一起遍历。由于没有给定求链表长度...

25. 复杂链表的复制 题目描述输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空） 思路注意本题的要点在于，输出结果中不要返回参数中的节点引用，所以不能直接将参数节点返回结果，而是要通过遍历的方式建立拥有新的节点的新链表。解题思路：1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;3、拆分链表，将链表拆分...

16. 合并两个排序的链表 题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 思路先判断输入的链表是否为空的指针。如果第一个链表为空，则直接返回第二个链表；如果第二个链表为空，则直接返回第一个链表。如果两个链表都是空链表，合并的结果是得到一个空链表。在python中可以用or来简化这一操作，直接初始化个空节点，当两个链表有为空的时候，thisNode.next = pHead1 or pHead2即可。两个链表都是排序好的，我们只需要从头遍历两个链表，判断在当前节点时，哪个链表中的值小，就复制哪个链表到结果链表中，再将指针往后移动，判断下个...

15. 反转链表 题目描述 输入一个链表，反转链表后，输出新链表的表头。思路 使用三个指针，分别指向当前遍历到的结点、它的前一个结点以及后一个结点。当前节点不为空时进行遍历：当前节点的next = 前一个节点lastNode（进行前后翻转）前一个节点(lastNode) = 当前节点（往后走一格）当前节点 = 当前节点的next（往后走一格）到最后当前节点为空，链表的首节点为lastNode代码实现 # -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # ...

14. 链表中倒数第k个结点 题目描述输入一个链表，输出该链表中倒数第k个结点。 思路定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。 代码实现 # -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = No...

3. 从尾到头打印链表 题目描述输入一个链表，按链表从尾到头的顺序返回一个ArrayList。 思路用python实现链表翻转输出，根据ListNode的定义，这是个单项的链表，只能从前往后遍历，先进后出思想，可以用栈，但python可以直接用插入首位的方法来做。 代码实现 # -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回从尾部到头部的列表值序列，例如...

53. 表示数值的字符串 题目描述请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。 思路在遍历的时候判断异常情况，参考@networkcpx的高赞答案 代码实现 # -*- coding:utf-8 -*- class Solution: # s字符串 def isNumeric(self, s): # write code here # 标记符...

52. 正则表达式匹配 题目描述请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配 思路看了@zxlly要offer的代码，才搞懂这道题的思路 这道题边界情况也有点多，首先判断s和pattern的长度，分出了四种情况，其中1.如果s与pattern都为空，则True；2.如果s不为空，而pattern为空，则False；3.如果s为空，而patter...

49. 把字符串转换成整数 题目描述将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。输入描述:输入一个字符串,包括数字字母符号,可以为空输出描述:如果是合法的数值表达则返回该数字，否则返回0 思路这道题需要考虑全面，对特殊情况经行处理，要判断的边界条件非常多，主要有：空字符串空字符、正负号、输入值的合法性(不能是字母标点)等。python不需要对溢出进行处理，源码会自行转换？。 代码实现 # -*- coding:utf-8 -...