# -*- coding:utf-8 -*-# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:
# 返回构造的TreeNode根节点defreConstructBinaryTree(self, pre, tin):
# write code hereifpre== []: returnNoneroot=TreeNode(pre[0])
cut=tin.index(pre[0]) ###直接取某值的位置root.left=self.reConstructBinaryTree(pre[1:cut+1], tin[:cut])
root.right=self.reConstructBinaryTree(pre[cut+1:], tin[cut+1:])
returnrootclassSolution:
# 返回构造的TreeNode根节点defreConstructBinaryTree(self, pre, tin):
# write code hereifpre== []:
returnNoneforiinrange(len(pre)):
iftin[i] ==pre[0]:
breakroot=TreeNode(pre[0])
#cut = tin.index(pre[0])root.left=self.reConstructBinaryTree(pre[1:i+1], tin[:i])
root.right=self.reConstructBinaryTree(pre[i+1:], tin[i+1:])
returnrootNOTE: None 不等同于空list
解题关键：熟悉二叉树遍历定义，前序遍历最先访问根结点，中序遍历访问完左子树，再访问根结点。
-*-coding:utf-8-*-classSolution:
def__init__(self):
self.stack1= []
self.stack2= []
defpush(self, node):
# write code hereself.stack1.append(node)
defpop(self):
# return xxifself.stack2!= []:
returnself.stack2.pop()
ifself.stack1== []:
returnNonewhileself.stack1!= []:
self.stack2.append(self.stack1.pop())
returnself.stack2.pop() #pop()自带对空list的处理解题思路：栈和队列的区别只在pop的时候有所体现，因此对删除元素的几种情形进行画图举例，即可得出解题思路。
# -*- coding:utf-8 -*-classSolution:
defminNumberInRotateArray(self, rarray):
# write code hereifrarray== []:
return0l=0r=len(rarray) -1ifrarray[l] <rarray[r]:
returnrarray[0]
while (r-l) >1:
mid= (l+r)/2if (rarray[l] ==rarray[r]) & (rarray[mid] ==rarray[l]): #此时无法判断最小元素可能出现在哪侧，因此无法缩小搜索范围returnself.minarray(rarray[l,r]) #顺序查找 O(n)ifrarray[mid] >=rarray[l]:
l=midelse:
r=midreturnrarray[r]
defminarray(self, array):
m=array[0]
foriinarray:
ifi<m:
m=ireturnm解题关键：首先分析旋转数组头尾数字（<, =, >）的三种情况，同时类排序数组联想到二分查找（头尾两根指针），再举例分析查找过程中mid对应数字相对于数组头尾元素的三种情况，统计规律，形成思路。
递归写法：简单但重复计算量大，超时。
# -*- coding:utf-8 -*-classSolution:
defFibonacci(self, n):
# write code hereifn==0:
return0ifn==1:
return1returnself.Fibonacci(n-1) +self.Fibonacci(n-2)
非递归写法：将重复计算以中间量暂存下来，节约计算量——迭代# -*- coding:utf-8 -*-# -*- coding:utf-8 -*-classSolution:
defFibonacci(self, n):
# write code hereifn==0:
return0ifn==1:
return1f1=0f2=1for_inrange(n-1):
f1, f2=f2, f1+f2returnf2知识点：菲波那切数列 f(n) = f(n-1) + f(n-2)
# -*- coding:utf-8 -*-classSolution:
defjumpFloor(self, number):
# write code heref1=1f2=1while (number>1):
f1, f2=f2, f1+f2number=number-1returnf2解题思路：从一级台阶开始归纳，一级只能先跳1，对应方法有f(0)=1种，2级可以先跳1，对应方法有f(2-1)种，也可以先跳2，对应方法有f(2-2)=f(0)=1种，，，f(n) = f(n-1) + f(n-2)
# -*- coding:utf-8 -*-classSolution:
defjumpFloorII(self, number):
# write code herel= [1]
whilenumber>1 :
l.append(sum(l))
number=number-1returnsum(l)解题思路：从一级台阶开始归纳，f(n) = f(n-1) + f(n-2) + ... + f(0),需要保存所有中间结果。
# -*- coding:utf-8 -*-classSolution:
defrectCover(self, number):
# write code hereifnumber==0:
return0f1=1f2=1whilenumber>1:
f1, f2=f2, f1+f2number=number-1returnf2解题思路：可以类比于跨台阶，横放小矩形时必须一次放两个，就相当于一步跨两个。因此还是斐波那契数列。
**错误解法：采用flag左移的方式时，由于python中的int是无限大的，会发生左移进入死循环的情况。
c++使用unsignedintflag进行循环限制。**# -*- coding:utf-8 -*-classSolution:
defNumberOf1(self, n):
# write code herecount=0flag=1while(flag):
if (n&flag):
count=count+1flag=flag<<1returncount# -*- coding:utf-8 -*-**手动进行位数限制**classSolution:
defNumberOf1(self, n):
# write code herecount=0flag=1for_inrange(32):
if (n&flag):
count=count+1flag=flag<<1returncount**右移解法:负数用补码表示。**# -*- coding:utf-8 -*-classSolution:
defNumberOf1(self, n):
# write code herecount=0ifn<0:
n=n&0xffffffffwhile(n):
if (n&1):
count=count+1n=n>>1returncount**将1逐个消除的解法，需要循环次数最少**# -*- coding:utf-8 -*-classSolution:
defNumberOf1(self, n):
# write code herebits=0ifn<0:
n=n&0xffffffff#python中负数使用-ob加原码表示，与0xffffffff（0b11111111111111111111111111111111）相与，不改变n的情况下，将n转成补码表示。whilen:
bits+=1n= (n-1) &nreturnbits知识点：位运算会把数字用二进制表示（并不会将操作符左右两边数字补成相同位数），可对每一位上的0或者1做与(&)、或(|)、异或(^)、左移(<<)、右移(>>)操作。需要注意的是左移n位操作直接丢弃最左边n位，最右边补上n个0；右移n位操作丢弃最右边n位，但是数字为正时最左边补n位0，数字为负时最左边补n位1。因此，需要特别注意位运算中负数情况的处理。
**普通解法：不能调用库函数（幂**），用乘法计算时需要考虑全面,base==0,exp==0,exp<0.**# -*- coding:utf-8 -*-classSolution:
defPower(self, base, exponent):
# write code hereifexponent==0:
return1ifbase==0:
return0re=1ifexponent>0:
for_inrange(exponent):
re=re*baseelifexponent<0:
for_inrange(-exponent):
re=re*basere=1/rereturnre# -*- coding:utf-8 -*-classSolution:
defpower(self, x, n):
ifn==0:
return1res=self.power(x, n>>1)
res=res*resif (n&1) ==0:
returnresreturnres*xdefPower(self, base, exponent):
# write code hereifexponent==0:
return1ifbase==0:
return0ifexponent>0:
returnself.power(base, exponent)
elifexponent<0:
return1/self.power(base, -exponent)优化解法：快速幂方法，将幂不断二分(eg:210=25 * 25)，O(logn)次循环。**
**空间换时间：遍历一遍存到两个list中。**# -*- coding:utf-8 -*-classSolution:
defreOrderArray(self, array):
# write code herel1= []
l2= []
foriinarray:
l1.append(i) if (i&1) elsel2.append(i)
returnl1+l2**利用sorted函数的高级用法**# -*- coding:utf-8 -*-classSolution:
defreOrderArray(self, array):
# write code herereturnsorted(array,key=lambdac:c&1,reverse=True)**遍历链表两次的解法，注意处理链表为空和k大于链表长度的情况。**# -*- coding:utf-8 -*-# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution:
defFindKthToTail(self, head, k):
# write code hereifhead==None:
returnNonephead=headcount=1while(head.next!=None):
count=count+1head=head.nextifcount<k:
returnNonefor_inrange(0, count-k):
phead=phead.nextreturnpheadclassSolution:
defFindKthToTail(self, head, k):
# write code hereslow=fast=headfor_inrange(k):
iffast==None:
returnNonefast=fast.nextwhile(fast):
slow, fast=slow.next, fast.nextreturnslow解题关键：采用快慢两根指针的解法，只需遍历链表一次。（常用技巧！）
# -*- coding:utf-8 -*-# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution:
# 返回ListNodedefReverseList(self, pHead):
# write code hereprev=Nonep=new=pHeadwhile(p):
new=p.nextp.next=prevprev=pp=newreturnprevclassSolution:
# 返回ListNodedefReverseList(self, pHead):
# write code hereprev=Nonewhile(pHead):
pHead.next, pHead, prev=prev, pHead.next, pHeadreturnprev善用python的赋值特性，使反转更简单。
# -*- coding:utf-8 -*-# class ListNode:# def __init__(self, x):# self.val = x# self.next = None**将链表2往链表1里逐个插入的迭代解法**classSolution:
# 返回合并后列表defMerge(self, pHead1, pHead2):
# write code hereifnotpHead2ornotpHead1:
returnpHead2orpHead1''' The and and or operators do return one of their operands, not a pure boolean value like True or False '''#p1 = ListNode(0)p1=pHead1while(pHead2andpHead1.next):
if (pHead2.val>pHead1.next.val):
pHead1=pHead1.nextelse:
pHead1.next, pHead2.next, pHead2=pHead2, pHead1.next, pHead2.nextpHead1=pHead1.nextifpHead1.next==None:
pHead1.next=pHead2returnp1**优化的迭代解法：逐个取当前最小值形成新链表——边界条件更容易处理。**classSolution:
# 返回合并后列表defMerge(self, pHead1, pHead2):
# write code here# The and and or operators do return one of their operands,# not a pure boolean value like True or FalseifnotpHead2ornotpHead1:
returnpHead2orpHead1p1=new=ListNode(0)
while(pHead2andpHead1):
ifpHead1.val<pHead2.val:
new.next, pHead1=pHead1, pHead1.nextelse:
new.next, pHead2=pHead2, pHead2.nextnew=new.nextnew.next=pHead1orpHead2returnp1.next**递归解法：清晰简洁，但是判断语句重复计算多次。**classSolution:
# 返回合并后列表defMerge(self, pHead1, pHead2):
# write code hereifpHead1==None:
returnpHead2ifpHead2==None:
returnpHead1ifpHead2.val<pHead1.val:
pHead2.next=self.Merge(pHead1, pHead2.next)
returnpHead2pHead1.next=self.Merge(pHead2, pHead1.next)
returnpHead1# -*- coding:utf-8 -*-# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:
defHasSubtree(self, pRoot1, pRoot2):
ifpRoot2==None:
returnFalseifpRoot1:
ifpRoot1.val==pRoot2.val:
if (self.issubtree(pRoot1.left, pRoot2.left) andself.issubtree(pRoot1.right, pRoot2.right)):
returnTruereturnself.HasSubtree(pRoot1.left, pRoot2) orself.HasSubtree(pRoot1.right, pRoot2)
returnFalsedefissubtree(self, p1, p2):
ifp2==None:
returnTrueifp1==None:
returnFalseifp1.val==p2.val:
returnself.issubtree(p1.left, p2.left) andself.issubtree(p1.right, p2.right)
returnFalse解题关键：嵌套两个递归，一个是递归遍历A树寻找与B树根节点相同的节点，一个是递归判断A树中该节点为根节点的子树是否和B树有相同结构。因此，要注意拆分成两个函数。
# -*- coding:utf-8 -*-# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:
# 返回镜像树的根节点defMirror(self, root):
# write code herejavascript:window.close();ifroot==None:
returnNoneroot.left=self.Mirror(root.left)
root.right=self.Mirror(root.right)
root.left, root.right=root.right, root.leftreturnroot递归：很常规，简单。
# -*- coding:utf-8 -*-# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:
# 返回镜像树的根节点defMirror(self, root):
# write code herejavascript:window.close();s= [root]
whiles:
r=s.pop()
ifr: r.left, r.right=r.right, r.lefts.append(r.left)
s.append(r.right)
returnroot迭代解法：利用栈(前序)或队列（层次）的存储特点进行迭代，常用技巧。
# -*- coding:utf-8 -*-classSolution:
# matrix类型为二维列表，需要返回列表defprintMatrix(self, matrix):
# write code herereturnmatrixand (list(matrix.pop(0)) +self.printMatrix(list(zip(*matrix))[::-1]))# -*- coding:utf-8 -*-classSolution:
def__init__(self):
self._stack= []
defpush(self, node):
# write code herem=self.min()
ifnode<m:
self._stack.append((node, node))
else:
self._stack.append((node, m))
defpop(self):
# write code hereself._stack.pop()
deftop(self):
# write code hereifself._stack:
returnself._stack[-1][0]
else:
returnNonedefmin(self):
# write code hereifself._stack:
returnself._stack[-1][-1]
else:
returnfloat('inf')空间换时间，存下栈不同状态时的最小值。
# -*- coding:utf-8 -*-classSolution:
defIsPopOrder(self, pushV, popV):
# write code herej=0s= []
fornuminpushV:
s.append(num)
whilej<len(popV) ands[-1] ==popV[j]:
s.pop()
j=j+1returns==[]引入辅助栈进行模拟
# -*- coding:utf-8 -*-# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:
# 返回从上到下每个节点值列表，例：[1,2,3]defPrintFromTopToBottom(self, root):
# write code hereres= []
s=rootand [root]
whiles:
res.append(s[0].val)
node=s.pop(0)
ifnode.left:
s.append(node.left)
ifnode.right:
s.append(node.right)
returnres利用队列存储特性，将节点进行逐层从左往右遍历。
classSolution:
# 返回从上到下每个节点值列表，例：[1,2,3]defPrintFromTopToBottom(self, root):
# write code hereans, level= [], rootand [root]
whilelevel:
ans+= [n.valforninlevel]
level= [kforninlevelforkin (n.left, n.right) ifk]
returnanspython列表表达式，使代码更pythonic。
# -*- coding:utf-8 -*-classSolution:
defVerifySquenceOfBST(self, sequence):
# write code hereifsequence== []:
returnFalsenode=sequence[-1]
index=len(sequence) -1foriinsequence:
ifi>node:
index=sequence.index(i)
breakleft=sequence[:index]
right=sequence[index:len(sequence)-1]
ifnotall(x>nodeforxinright):
returnFalsef_left=f_right=Trueifleft:
f_left=self.VerifySquenceOfBST(left)
ifright:
f_right=self.VerifySquenceOfBST(right)
returnf_leftandf_right解题思路：抓住二叉树后序遍历和二叉搜索树的特性。 二叉排序树的性质：左子树上所有节点的值均小于它的根节点；右子树上所有节点的值均大于它的根节点。 二叉排序树后序遍历的性质：序列最后一个数字是根节点，序列剩余部分分成两部分，前一部分是左子树，后一部分是右子树。