本系列博文為題庫刷題筆記，（僅在督促自己刷題）如有不詳之處，請參考leetcode官網：https://leetcode-cn.com/problemset/lcof/
172/1645-184/1645

編程語言為python

21.面試題22-鏈表中的倒數第k個節點

輸入一個鏈表，輸出該鏈表中倒數第k個節點。為了符合大多數人的習慣，本題從1開始計數，即鏈表的尾節點是倒數第1個節點。例如，一個鏈表有6個節點，從頭節點開始，它們的值依次是1、2、3、4、5、6。這個鏈表的倒數第3個節點是值為4的節點。
雙指針技巧，沒要求刪除節點，所以不需要設置啞節點

class Solution(object):def getKthFromEnd(self, head, k):""":type head: ListNode:type k: int:rtype: ListNode"""if head==None:return headp1=headfor _ in range(k): # 1:[0,k-1]p1=p1.nextp2=headwhile(p1):p1=p1.nextp2=p2.nextreturn p2

22.面試題24-反轉鏈表

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def reverseList(self, head):""":type head: ListNode:rtype: ListNode"""if head==None or head.next==None:return headpre_node=Nonecur_node=headwhile(cur_node):next_node=cur_node.nextcur_node.next=pre_nodepre_node=cur_nodecur_node=next_nodereturn pre_node

23.面試題25-合并兩個排序鏈表-遞歸

迭代：新建一個頭節點，用歸并方法比較連個排序鏈表對應節點，用較小的節點值 創建新的節點；更新比較節點。
遞歸：

class Solution(object):def mergeTwoLists(self, l1, l2):""":type l1: ListNode:type l2: ListNode:rtype: ListNode"""if l1==None:return l2if l2==None:return l1if l1.val<=l2.val:l1.next=self.mergeTwoLists(l1.next,l2)return l1else:l2.next=self.mergeTwoLists(l1,l2.next)return l2

24.面試題26-樹的子結構

輸入兩棵二叉樹A和B，判斷B是不是A的子結構。(約定空樹不是任意一個樹的子結構)
B是A的子結構， 即 A中有出現和B相同的結構和節點值。

深度優先遍歷，比較各個節點。

A的每一個節點都可能是B的根節點，因此：
需要對A的每一個節點進行先序遍歷–isSubStructure(A,B)
以A每一個節點為根節點的子樹是否包含樹B-- dfs(node1,node2)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def isSubStructure(self, A, B):""":type A: TreeNode:type B: TreeNode:rtype: bool"""def dfs(node1,node2):if node2==None:return Trueif node1==None or node1.val!=node2.val:return Falsereturn dfs(node1.left,node2.left) or dfs(node1.right,node2.right) return bool(A and B) and (dfs(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))

25.面試題27-二叉樹的鏡像

請完成一個函數，輸入一個二叉樹，該函數輸出它的鏡像。
深度優先遍歷？
單個節點要作的操作:交換左右子樹,對兩個子樹進行相同的操作。

class Solution(object):def mirrorTree(self, root):""":type root: TreeNode:rtype: TreeNode"""def dfs(node):if node==None:returnnode.left,node.right=node.right,node.leftdfs(node.left)dfs(node.right)return nodereturn dfs(root)

26.面試題28-對稱二叉樹

請實現一個函數，用來判斷一棵二叉樹是不是對稱的。如果一棵二叉樹和它的鏡像一樣，那么它是對稱的。
迭代解法：

class Solution(object):def isSymmetric(self, root):""":type root: TreeNode:rtype: bool"""que=[(root,root)]while(que):node1,node2=que.pop(0)if node1==None and node2==None:continueif node1==None or node2==None:return Falseif node1.val!=node2.val:return Falseque.append((node1.left,node2.right))que.append((node1.right,node2.left))return True

自底向上的遞歸：子樹給父親提供信息

class Solution(object):def isSymmetric(self, root):""":type root: TreeNode:rtype: bool"""def isSymmetric_bottom_up(node1,node2):if node1==None and node2==None:return Trueif node1==None or node2==None:return Falsereturn node1.val==node2.val and isSymmetric_bottom_up(node1.left,node2.right) and isSymmetric_bottom_up(node1.right,node2.left)return isSymmetric_bottom_up(root,root)

27.面試題29-順時針打印矩陣

有一個控制方向的列表

class Solution(object):def spiralOrder(self, matrix):""":type matrix: List[List[int]]:rtype: List[int]"""m=len(matrix)if m==0:return []n=len(matrix[0])visited_mat=[[True]*n for _ in range(m)]dr=[0,1,0,-1]dc=[1,0,-1,0]di=0r,c=0,0res=[]for _ in range(m*n):res.append(matrix[r][c])visited_mat[r][c]=Falsenext_r,next_c=r+dr[di],c+dc[di] # 控制橫縱坐標的增減# print(r,c,next_r,next_c)if 0<=next_r<m and 0<=next_c<n and visited_mat[next_r][next_c]:r=next_rc=next_celse:di=(di+1)%4r,c=r+dr[di],c+dc[di]return res

28.面試題30-包含min函數的棧

定義棧的數據結構，請在該類型中實現一個能夠得到棧的最小元素的 min 函數在該棧中，調用 min、push 及 pop 的時間復雜度都是 O(1)。
min 函數，時間復雜度要求是o(1),要么存一個元素，要么放在輔助棧的棧頂或棧底，維護一個元素在連續彈出元素的時候無法o(1)時間更新最小值。

所以需要維護以個輔助棧，輔助棧棧頂存最小元素。
當push val時，將val與輔助棧棧頂元素對比：如果更小就Push進輔助棧棧頂 ；如果更大就復制一份棧頂元素；
當pop元素時，兩個棧同時pop()就可以了。

class MinStack(object):def __init__(self):"""initialize your data structure here."""self.main_stack=[]self.help_stack=[]self.size=0def push(self, x):""":type x: int:rtype: None"""if self.size==0:self.size+=1self.main_stack.append(x)self.help_stack.append(x)else:self.size+=1self.main_stack.append(x)if self.help_stack[-1]>x:self.help_stack.append(x)else:self.help_stack.append(self.help_stack[-1])def pop(self):""":rtype: None"""if self.size==0:returnelse:self.size-=1self.help_stack.pop()return self.main_stack.pop()def top(self):""":rtype: int"""if self.size==0:return else:return self.main_stack[-1]def min(self):""":rtype: int"""if self.size==0:returnelse:return self.help_stack[-1]

29.面試題31-棧的押入，彈出序列

輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如，序列 {1,2,3,4,5} 是某棧的壓棧序列，序列 {4,5,3,2,1} 是該壓棧序列對應的一個彈出序列，但 {4,3,5,1,2} 就不可能是該壓棧序列的彈出序列。

使用一個輔助棧來幫助實現判斷：
入棧：按照壓棧序列順序執行，每次入棧后，判斷棧頂元素和彈出序列的當前元素是否一致，一致的話，執行彈出操作。不斷重復，如果能夠遍歷完兩個序列，說明兩者是棧的押入和彈出序列：

class Solution(object):def validateStackSequences(self, pushed, popped):""":type pushed: List[int]:type popped: List[int]:rtype: bool"""help_stack=[]i=0for val in pushed:help_stack.append(val)while(help_stack and help_stack[-1]==popped[i]):help_stack.pop()i+=1return not help_stack

30.面試題32-1-從上到下打印二叉樹

從上到下打印出二叉樹的每個節點，同一層的節點按照從左到右的順序打印。結果放在一個list中。
思路：二叉樹的層次遍歷。迭代-沒有level的控制，一直押入彈出就可以。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def levelOrder(self, root):""":type root: TreeNode:rtype: List[int]"""if root==None:return []res=[]que=[root]while(que):node=que.pop(0) # 不加可以么res.append(node.val)if node.left:que.append(node.left)if node.right:que.append(node.right)return res

31.面試題32-2-從上到下打印二叉樹

從上到下按層打印二叉樹，同一層的節點按從左到右的順序打印，每一層打印到一行。
思路：二叉樹的層次遍歷。迭代，維護每一層的節點在同一個循環中輸出。

class Solution(object):def levelOrder(self, root):""":type root: TreeNode:rtype: List[List[int]]"""if root==None:return []res=[]que=[root]while(que):n=len(que)res.append([])for i in range(n):node=que.pop(0)res[-1].append(node.val)if node.left:que.append(node.left)if node.right:que.append(node.right)return res

遞歸：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def levelOrder(self, root):""":type root: TreeNode:rtype: List[List[int]]"""def bfs(node,level):if node==None:returnif level>len(res)-1:res.append([])res[level].append(node.val)bfs(node.left,level+1)bfs(node.right,level+1)res=[]bfs(root,0) # 如果root為空會直接返回return res

32.面試題32-3-從上到下打印二叉樹

請實現一個函數按照之字形順序打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右到左的順序打印，第三行再按照從左到右的順序打印，其他行以此類推。
最直接的辦法：依據上一題的解題思路，只是在奇數層的時候將res[l]內容逆序操作以下。

class Solution(object):def levelOrder(self, root):""":type root: TreeNode:rtype: List[List[int]]"""if root==None:return []res=[]que=[root]while(que):n=len(que)tmp=[]for i in range(n):node=que.pop(0)tmp.append(node.val)if node.left:que.append(node.left)if node.right:que.append(node.right)if len(res)%2==1:res.append(tmp[::-1])else:res.append(tmp)return res