一、數(shù)組

存放在連續(xù)內(nèi)存空間上相同數(shù)據(jù)類型的集合，可以通過(guò)下標(biāo)索引取到對(duì)應(yīng)的數(shù)據(jù)

1.1 二分查找

二分查找：要求數(shù)組是有序且沒有重復(fù)的元素

1.1.1 二分查找

題目：leetcode 704

思路：二分查找

class Solution(object):def search(self, nums, target):left = 0right = len(nums) - 1while (left <= right):mid = left + (right - left) / 2if nums[mid] == target:return midelif nums[mid] > target:right = mid - 1else:left = mid + 1return -1

1.1.2 搜索插入位置

題目：leetcode 35

思路：二分

class Solution(object):def searchInsert(self, nums, target):left = 0right = len(nums) - 1while left <= right:mid = left + (right - left) / 2if nums[mid] == target:return midelif nums[mid] > target:right = mid - 1else:left = mid + 1return right + 1

1.1.3 排序數(shù)組中查找元素第一和最后一個(gè)位置

題目：leetcode 34
思路：

• 1、找第一個(gè)位置：先二分模板，然后思考相等以后什么時(shí)候要往左找？——在mid-1上的元素如果都大于等于target時(shí)（需要確保mid-1合法），說(shuō)明第一個(gè)位置還在左邊。否則mid位置就是第一個(gè)。找不到就是-1。
• 2、找最后一個(gè)位置：先二分模板，然后思考相等以后什么時(shí)候要往右找？——在mid+1上的元素小于等于target時(shí)（需要確保mid+1合法），說(shuō)明最后一個(gè)位置還在右邊。否則mid位置就是最后一個(gè)。找不到就是-1

class Solution(object):def search_first(self, nums, target):left = 0right = len(nums) - 1while (left <= right):mid = left + (right - left) / 2if nums[mid] == target:if mid > 1 and nums[mid-1] >= target:right = mid - 1else:return midelif nums[mid] < target:left = mid + 1else:right = mid - 1return -1def search_right(self, nums, target):left = 0right = len(nums) - 1while (left <= right):mid = left + (right - left) / 2if nums[mid] == target:if mid < len(nums) - 1 and nums[mid+1] <= target:left = mid + 1else:return midelif nums[mid] > target:right = mid - 1else:left = mid + 1return -1def searchRange(self, nums, target):left = self.search_first(nums, target)right = self.search_right(nums, target)return [left, right]

1.1.4 x的平方根

題目：leetcode 69

思路：最終結(jié)果一定是在0到x之間，所以可以用二分。比如中間要找的數(shù)是k，那么左區(qū)間滿足k平方小于等于x，右區(qū)間k平方大于x。也就是，如果k平方小于等于x，那么k有可能是結(jié)果，所以把區(qū)間縮小到右區(qū)間。如果k平方大于x，那么k不可能是是結(jié)果，所以把區(qū)間縮小到左區(qū)間。一直二分直到左右指針相遇返回結(jié)果

class Solution(object):def mySqrt(self, x):left = 0right = xans = -1while left <= right:mid = left + (right - left) / 2if mid * mid < x:left = mid + 1ans = midelif mid * mid > x:right = mid - 1else:left = mid + 1ans = midreturn ans

1.1.5 有效的完全平方數(shù)

題目：leetcode 367

思路：同1.1.4

class Solution:def isPerfectSquare(self, num):left, right = 0, numwhile left <= right:mid = left + (right - left) / 2square = mid * midif square < num:left = mid + 1elif square > num:right = mid - 1else:return Truereturn False

1.2 快慢指針

1.2.1 移除元素

題目：leetcode 27

思路：使用快慢指針，快指針：獲取數(shù)組元素；慢指針：獲取新數(shù)組中需要更新的位置

class Solution(object):def removeElement(self, nums, val):fast = 0slow = 0for fast in range(0, len(nums)):if nums[fast] != val:nums[slow] = nums[fast]slow += 1return slow

1.2.2 刪除有序數(shù)組中的重復(fù)項(xiàng)

題目：leetcode 26

思路：快慢指針

class Solution(object):def removeDuplicates(self, nums):slow = 1num = nums[0]for fast in range(1, len(nums)):if nums[fast] != num:nums[slow] = nums[fast]num = nums[fast]slow += 1return slow

1.2.3 移動(dòng)0

題目：leetcode 283

思路：快慢指針，快指針找到不為0的和慢指針上的元素交換

class Solution(object):def moveZeroes(self, nums):slow = 0fast = 0for fast in range(0, len(nums)):if nums[fast] != 0:tmp = nums[slow]nums[slow] = nums[fast]nums[fast] = tmpslow += 1

1.2.4 比較含退格的字符串

題目：leetcode 844

思路：分別記錄兩個(gè)字符串中退格的個(gè)數(shù)。i、j指針從后往前遍歷，目的是把退格跳過(guò)，然后比較i和j上的元素

class Solution(object):def backspaceCompare(self, s, t):i = len(s) - 1j = len(t) - 1skip_s = 0skip_t = 0while (i >= 0 and j >= 0):while i >= 0:if s[i] == '#':skip_s += 1else:if skip_s > 0:skip_s -= 1else:breaki -= 1while j >= 0:if t[j] == '#':skip_t += 1else:if skip_t > 0:skip_t -= 1else:breakj -= 1if s[i] != t[j]:return Falsei -= 1j -= 1return True

1.2.5 有序數(shù)組的平方

題目：leetcode 977

思路：從后往前遍歷，保證最后的數(shù)是最大的，中間做元素交換和覆蓋即可

class Solution(object):def sortedSquares(self, nums):right = len(nums) - 1while right >= 0:l_value = abs(nums[0] * nums[0])r_value = abs(nums[right] * nums[right])if l_value > r_value:nums[0] = nums[right]nums[right] = l_valueelse:nums[right] = r_valueright -= 1return nums

1.3 滑動(dòng)窗口

1.3.1 長(zhǎng)度最小的子數(shù)組

題目：leetcode 209

思路：滑動(dòng)窗口，j表示終止位置，i表示起始位置。終止位置不斷移動(dòng)求和，當(dāng)發(fā)現(xiàn)其和大于等于目標(biāo)值時(shí)，不斷移動(dòng)起始位置，另外減少和，在這個(gè)過(guò)程中計(jì)算出窗口的最小長(zhǎng)度即可。特殊情況是所有加起來(lái)都沒有大于目標(biāo)值，那么對(duì)這種情況返回0即可

class Solution(object):def minSubArrayLen(self, target, nums):i = 0s = 0result = len(nums)flag = Falsefor j in range(0, len(nums)):s = s + nums[j]while (s >= target):flag = Truesub_len = j - i + 1result = min(result, sub_len)s = s - nums[i]i = i + 1return result if flag else 0

1.3.2 水果成籃

題目：leetcode 904

思路：這里fruits中的每個(gè)元素代表第i棵樹上的水果種類，而不是種類數(shù)。所以只要保證兩個(gè)籃子里裝了兩個(gè)種類的水果即可。右指針從0開始，把水果撿進(jìn)籃子，籃子內(nèi)只要超過(guò)2個(gè)，就開始去丟最左邊的水果，丟了之后移動(dòng)左指針，然后計(jì)算最大距離即可

class Solution(object):def totalFruit(self, fruits):bucket = defaultdict(int)res = left = right = 0for right in range(len(fruits)):bucket[fruits[right]] += 1while (len(bucket) > 2):bucket[fruits[left]] -= 1if bucket[fruits[left]] == 0:del bucket[fruits[left]]left += 1res = max(res, right - left + 1)return res

1.3.3 最小覆蓋字串

題目：leetcode 76

思路：定義ht存儲(chǔ)t中字符的數(shù)量{A: 1, B: 1, C: 1}，hs存儲(chǔ)s中每個(gè)，cnt記錄當(dāng)前字符的數(shù)量。移動(dòng)窗口過(guò)程中加入元素時(shí)如果沒超過(guò)ht中字符的數(shù)量，說(shuō)明是一個(gè)有效字符，把cnt值加1

class Solution(object):def minWindow(self, s, t):""":type s: str:type t: str:rtype: str"""if len(t) > len(s):return ""# hs統(tǒng)計(jì)當(dāng)前窗口中各個(gè)字符的數(shù)量hs = collections.defaultdict(int)ht = collections.defaultdict(int)# 統(tǒng)計(jì)t中各字符數(shù)量到ht中for char in t:ht[char] += 1j = i = 0cnt = 0res_sub_str = ""min_length = len(s) + 1# 移動(dòng)右邊指針for j in range(len(s)):# 往hs添加當(dāng)前字符hs[s[j]] += 1# 如果添加的字符沒有超過(guò)ht中對(duì)應(yīng)字符的數(shù)量，那么有效字符+1if hs[s[j]] <= ht[s[j]]:cnt += 1# 看是否移動(dòng)左邊指針，當(dāng)hs中對(duì)應(yīng)元素的數(shù)量大于ht中對(duì)應(yīng)元素的數(shù)量，說(shuō)明是冗余字符，需要?jiǎng)h去且左指針往前走while i <= j and hs[s[i]] > ht[s[i]]:hs[s[i]] -= 1i += 1# 當(dāng)有效字符數(shù)和t的長(zhǎng)度相同，那么更新最小窗口大小，并取窗口內(nèi)的子字符串if cnt == len(t):if (j - i + 1) < min_length:min_length = j - i + 1res_sub_str = s[i:j+1]return res_sub_str

1.4 螺旋矩陣

題目：leetcode 59

思路：模擬順時(shí)針畫矩陣，填充數(shù)組。設(shè)置偏移量為邊界，每個(gè)區(qū)間都是左閉右開，循環(huán)次數(shù)loop應(yīng)小于n的一半，每次loop完，應(yīng)該將起始坐標(biāo)x和y沿對(duì)角線移動(dòng)。最后，如果n是奇數(shù)，應(yīng)該在循環(huán)結(jié)束時(shí)將中心元素填充進(jìn)去，此時(shí)x和y已經(jīng)移動(dòng)到了中心點(diǎn)

class Solution(object):def generateMatrix(self, n):""":type n: int:rtype: List[List[int]]"""m = [[0] * n for i in range(0, n)]loop = 0i = j = 0start_row = start_col = 0offset = 1num = 1while loop < n / 2:for j in range(start_col, n - offset):m[start_row][j] = numnum += 1j += 1for i in range(start_row, n - offset):m[i][j] = numnum += 1i += 1for j in range(j, start_col, -1):m[i][j] = numnum += 1j -= 1for i in range(i, start_row, -1):m[i][j] = numnum += 1i -= 1start_row += 1start_col += 1offset += 1loop += 1if n % 2 == 1:m[start_row][start_col] = numreturn m

二、鏈表

鏈表是通過(guò)指針串聯(lián)在一起的線性結(jié)構(gòu)，但在內(nèi)存中不是連續(xù)分布的，分配機(jī)制取決于os的內(nèi)存管理。

每個(gè)節(jié)點(diǎn)由數(shù)據(jù)域和指針域組成，類型有

• 單鏈表
• 雙鏈表：每個(gè)節(jié)點(diǎn)有兩個(gè)指針域，分別指向前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)
• 循環(huán)鏈表：鏈表首尾相連，通常解決約瑟夫環(huán)的問(wèn)題

對(duì)比數(shù)組（插入/刪除O(n)，查詢O(1)），鏈表的時(shí)間復(fù)雜度為（插入/刪除O(1)，查詢O(n)）

鏈表長(zhǎng)度不固定，適合頻繁增刪，較少查詢的場(chǎng)景

class ListNode:def __init__(self, val, next=None):self.val = valself.next = next

2.1 移除鏈表元素

題目：leetcode 203

思路：有兩種方式

• 直接在原鏈表進(jìn)行刪除操作：其他節(jié)點(diǎn)都是通過(guò)前一個(gè)節(jié)點(diǎn)來(lái)刪除當(dāng)前節(jié)點(diǎn)的，頭節(jié)點(diǎn)沒有前一個(gè)節(jié)點(diǎn)，操作比較難統(tǒng)一
• 設(shè)置一個(gè)虛擬頭節(jié)點(diǎn)再進(jìn)行刪除操作：統(tǒng)一刪除操作，從鏈表最前端dummy節(jié)點(diǎn)開始判斷下一個(gè)元素是否和val相同，相同則進(jìn)行刪除操作并移動(dòng)指針，否則移動(dòng)當(dāng)前指針到下一個(gè)元素

常規(guī)刪除：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def removeElements(self, head, val):""":type head: ListNode:type val: int:rtype: ListNode"""if head is None:return Nonedummy = ListNode(next=head)cur = dummywhile cur.next is not None:if cur.next.val == val:cur.next = cur.next.nextelse:cur = cur.nextreturn dummy.next

遞歸刪除：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def removeElements(self, head, val):""":type head: ListNode:type val: int:rtype: ListNode"""if head is None:return Nonehead.next = self.removeElements(head.next, val)if head.val == val:return head.nextelse:return head

2.2 設(shè)計(jì)鏈表

題目：leetcode 707

思路：如代碼所示，添加和刪除都是先找到位置，斷開原鏈，加上新鏈

class ListNode(object):def __init__(self, val=0, next=None):self.val = valself.next = nextclass MyLinkedList(object):def __init__(self):self.dummy = ListNode()self.size = 0def get(self, index):"""校驗(yàn)index合法性，從虛擬頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)開始遍歷鏈表取值即可"""if index < 0 or index >= self.size:return -1cur = self.dummy.nextfor idx in range(0, index):cur = cur.nextreturn cur.valdef addAtHead(self, val):"""讓dummy節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是頭節(jié)點(diǎn)即可"""self.dummy.next = ListNode(val=val)self.size += 1def addAtTail(self, val):"""遍歷到最后一個(gè)節(jié)點(diǎn)，在最后一個(gè)節(jié)點(diǎn)后面新增一個(gè)節(jié)點(diǎn)即可"""cur = self.dummywhile cur.next is not None:cur = cur.nextcur.next = ListNode(val=val)self.size += 1def addAtIndex(self, index, val):"""新增節(jié)點(diǎn)時(shí)，遍歷到要添加的位置，讓當(dāng)前節(jié)點(diǎn)的next指向新節(jié)點(diǎn)，新節(jié)點(diǎn)的next是當(dāng)前節(jié)點(diǎn)的next"""if index < 0 or index >= self.size:returncur = self.dummyfor idx in range(0, index):cur = cur.nextcur.next = ListNode(val=val, next=cur.next)self.size += 1def deleteAtIndex(self, index):"""刪除節(jié)點(diǎn)時(shí)，遍歷到要?jiǎng)h除的位置，讓當(dāng)前節(jié)點(diǎn)的next指向下下個(gè)節(jié)點(diǎn)即可"""if index < 0 or index >= self.size:returncur = self.dummyfor idx in range(0, index):cur = cur.nextcur.next = cur.next.nextself.size -= 1# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

2.3 反轉(zhuǎn)鏈表

題目：leetcode 206

思路：減少空間浪費(fèi)，原地反轉(zhuǎn)

方案1:雙指針?lè)?#xff0c;初始位置，pre指針指向空，cur指向頭節(jié)點(diǎn)，每次循環(huán)保存cur的下一個(gè)節(jié)點(diǎn)到tmp，改變cur的next指向到pre，然后移動(dòng)pre指針，移動(dòng)cur指針，直到cur為空時(shí)返回pre指針即可

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def reverseList(self, head):""":type head: ListNode:rtype: ListNode"""cur = headpre = Nonewhile cur:tmp = cur.nextcur.next = prepre = curcur = tmpreturn pre

方案2:遞歸法，和雙指針?lè)ㄒ粯拥乃悸?#xff0c;遞歸初始，pre指針指向空，cur指向頭節(jié)點(diǎn)，每次遞歸保存cur的下一個(gè)節(jié)點(diǎn)到tmp，改變cur的next指向到pre，然后移動(dòng)pre指針，移動(dòng)cur指針，直到cur為空時(shí)結(jié)束遞歸返回pre即可

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def reverse(self, pre, cur):if cur is None:return pretmp = cur.nextcur.next = prepre = curcur = tmpreturn self.reverse(pre, cur)def reverseList(self, head):return self.reverse(None, head)

2.4 兩兩交換鏈表中的節(jié)點(diǎn)

題目：leetcode 24

方案1:

• 思路：設(shè)定頭節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)為頭節(jié)點(diǎn)，暫存1、2、3號(hào)元素，把cur指向2，2指向1，1指向3，最后cur往前走兩步，直到cur的next和next、next有一個(gè)為空則停止

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def swapPairs(self, head):dummy = ListNode(next=head)cur = dummy# 必須有cur的下一個(gè)和下下個(gè)才能交換，否則說(shuō)明已經(jīng)交換結(jié)束了while cur.next and cur.next.next:tmp1 = cur.nexttmp2 = cur.next.nexttmp3 = cur.next.next.nextcur.next = tmp2tmp2.next = tmp1tmp1.next = tmp3cur = cur.next.nextreturn dummy.next

方案2:

• 思路：遞歸，不使用頭節(jié)點(diǎn)，pre指向頭節(jié)點(diǎn)，cur指向head.next，next是head.next.next，每次交換pre和cur，然后把nxt當(dāng)作頭節(jié)點(diǎn)繼續(xù)交換，最后返回cur

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def swapPairs(self, head):if head is None or head.next is None:return headpre = headcur = head.nextnxt = head.next.nextcur.next = prepre.next = self.swapPairs(nxt)return cur

2.5 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)

題目：leetcode 19

思路：使用快慢指針，快慢指針同時(shí)指向dummy虛擬頭節(jié)點(diǎn)，快指針先走，走到頭了慢指針就可以刪了

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def removeNthFromEnd(self, head, n):dummy = ListNode(next=head)fast = slow = dummywhile n >= 0 and fast:fast = fast.nextn -= 1while fast:fast = fast.nextslow = slow.nextslow.next = slow.next.nextreturn dummy.next

2.6 鏈表相交

題目：leetcode 160

思路：先尾對(duì)齊兩個(gè)鏈表（求長(zhǎng)度差讓cur A先走），對(duì)齊以后一起走直到兩個(gè)指針指向同一個(gè)元素即可

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def getListNodeLen(self, head):l = 0cur = headwhile cur:cur = cur.nextl += 1return ldef run(self, head, n):cur = headfor i in range(0, n):cur = cur.nextreturn curdef getIntersectionNode(self, headA, headB):len_a = self.getListNodeLen(headA)len_b = self.getListNodeLen(headB)fast = slow = Noneif len_a > len_b:fast = self.run(headA, len_a - len_b)slow = headBelse:fast = self.run(headB, len_b - len_a)slow = headAwhile fast and slow:if fast == slow:return fastfast = fast.nextslow = slow.nextreturn None

2.7 環(huán)形鏈表

題目：leetcode 142

方案1:

• 直接用set，看是否已存在，存在即可返回

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def detectCycle(self, head):visited = set()cur = headwhile cur:if cur in visited:return curvisited.add(cur)cur = cur.nextreturn None

方案2:

• 快慢指針：快指針走兩步、慢指針走一步，相遇則說(shuō)明鏈表有環(huán)。相遇以后，慢指針回頭，快慢指針一步一步走，直到相遇則為環(huán)入口

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def detectCycle(self, head):fast = slow = headwhile fast and fast.next:fast = fast.next.nextslow = slow.nextif fast == slow:slow = headwhile slow != fast:slow = slow.nextfast = fast.nextreturn slowreturn None

三、哈希表

哈希表一般用來(lái)快速判斷一個(gè)元素是否出現(xiàn)在集合里，時(shí)間復(fù)雜度是O(1)

• 把元素通過(guò)哈希函數(shù)映射為哈希表上的索引，就可以通過(guò)索引下標(biāo)快速定位到該元素
• 數(shù)據(jù)結(jié)構(gòu)：數(shù)組、set、map等

當(dāng)元素的個(gè)數(shù)大于哈希表的大小時(shí)，就容易出現(xiàn)哈希碰撞

3.1 哈希碰撞

指兩個(gè)以上的元素都映射到了同一個(gè)位置，解決方法（拉鏈法、線性探測(cè)法）

1、拉鏈法

• 發(fā)生沖突的元素都存在同一位置的鏈表上
• 需要我們適當(dāng)選擇哈希表的大小，既不會(huì)因?yàn)閿?shù)組空而浪費(fèi)內(nèi)存，也不會(huì)因?yàn)殒湵硖L(zhǎng)而在查找上花太多時(shí)間

2、線性探測(cè)法

• 沖突后，就向下找一個(gè)空位放沖突的元素

3.2 有效的字母異位詞

題目：leetcode 242

思路：使用哈希表來(lái)記錄每個(gè)元素出現(xiàn)的次數(shù)

class Solution(object):def isAnagram(self, s, t):""":type s: str:type t: str:rtype: bool"""record = [0] * 26for i in range(0, len(s)):record[ord(s[i]) - ord('a')] += 1for i in range(0, len(t)):record[ord(t[i]) - ord('a')] -= 1for i in range(0, len(record)):if record[i] != 0:return Falsereturn True

或者使用defaultdict也可以

class Solution(object):def isAnagram(self, s, t):""":type s: str:type t: str:rtype: bool"""from collections import defaultdictrecord = defaultdict(int)for i in range(0, len(s)):record[s[i]] += 1for i in range(0, len(t)):record[t[i]] -= 1for k, v in record.items():if v != 0:return Falsereturn True

3.3 字母異位詞分組

題目：leetcode 49

思路：遍歷每個(gè)元素，對(duì)每個(gè)元素排序放到列表中即可

class Solution(object):def groupAnagrams(self, strs):""":type strs: List[str]:rtype: List[List[str]]"""from collections import defaultdictret = []m = defaultdict(list)for i in range(0, len(strs)):l = list(strs[i])sort_key = "".join(sorted(l))m[sort_key].append(strs[i])for k, v in m.items():ret.append(v)return ret

3.4 找到字符串中所有字母異位詞

題目：leetcode 438

思路：遍歷取子串看是否異位詞即可

class Solution(object):def is_ok(self, s1, s2):s1 = "".join(sorted(list(s1)))s2 = "".join(sorted(list(s2)))return s1 == s2def findAnagrams(self, s, p):ret = []for i in range(0, len(s)-len(p)+1):sub = s[i:i+len(p)]if self.is_ok(sub, p):ret.append(i)return ret

3.5 贖金信

題目：leetcode 383

思路：記錄一個(gè)單詞出現(xiàn)的次數(shù)，再遍歷另一個(gè)單詞，減去出現(xiàn)的次數(shù)，如果出現(xiàn)負(fù)數(shù)，說(shuō)明不能組成

class Solution(object):def canConstruct(self, ransomNote, magazine):from collections import defaultdictm = defaultdict(int)for i in range(0, len(magazine)):m[magazine[i]] += 1for i in range(0, len(ransomNote)):m[ransomNote[i]] -= 1for k, v in m.items():if v < 0:return Falsereturn True

3.6 兩個(gè)數(shù)組的交集

題目：leetcode 349

思路：使用set

class Solution(object):def intersection(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""m = dict()ret = set()for item in nums1:m[item] = 1for item in nums2:if m.get(item):ret.add(item)return list(ret)class Solution(object):def intersection(self, nums1, nums2):return list(set(nums1) & set(nums2))

用數(shù)組存兩個(gè)列表的元素，長(zhǎng)度取最大元素，兩個(gè)位置的元素相乘看是否為0

class Solution(object):def intersection(self, nums1, nums2):l = max(max(nums1), max(nums2)) + 1m1 = [0] * lm2 = [0] * lfor item in nums1:m1[item] += 1for item in nums2:m2[item] += 1ret = []for i in range(0, l):if m1[i] * m2[i] > 0:ret.append(i)return ret

3.7 快樂(lè)數(shù)

題目：leetcode 202

思路：求和時(shí)，通過(guò)模10獲取整數(shù)每一位上的數(shù)字，然后除以10更新數(shù)字；每一輪看求和數(shù)是否出現(xiàn)在哈希表中即可判斷是否進(jìn)入死循環(huán)

class Solution(object):def get_sum(self, n):s = 0while n > 0:num = n % 10s += num * numn = n / 10return sdef isHappy(self, n):visited = set()while True:s = self.get_sum(n)print n, sif s == 1:return Trueif s in visited:return Falseelse:visited.add(s)n = sreturn False            

3.8 兩數(shù)之和

題目：leetcode 1

思路：

方法1:使用哈希表存儲(chǔ)，key是元素，value是元素的下標(biāo)；遍歷數(shù)組每個(gè)元素，通過(guò)做差找到數(shù)據(jù)下標(biāo)返回即可

class Solution(object):def twoSum(self, nums, target):m = dict()for i in range(0, len(nums)):visited_value = target - nums[i]if visited_value in m:return [i, m[visited_value]]else:m[nums[i]] = ireturn [0, 0]

方法2:暴力

class Solution(object):def twoSum(self, nums, target):for i in range(0, len(nums)):for j in range(i+1, len(nums)):if nums[i] + nums[j] == target:return [i, j]return [0, 0]

3.9 四數(shù)相加II

題目：leetcode 454

思路：先去遍歷2個(gè)數(shù)組，統(tǒng)計(jì)他們所有元素相加的和以及出現(xiàn)的次數(shù)放到字典中，再去遍歷另外兩個(gè)數(shù)組，判斷0和另外兩個(gè)數(shù)組任意兩個(gè)元素之和的差值是否在字典中，如果在，那么獲取這個(gè)次數(shù)疊加。最后返回統(tǒng)計(jì)值即可

class Solution(object):def fourSumCount(self, nums1, nums2, nums3, nums4):""":type nums1: List[int]:type nums2: List[int]:type nums3: List[int]:type nums4: List[int]:rtype: int"""n = len(nums1)m = dict()for i in range(0, n):for j in range(0, n):s = nums1[i] + nums2[j]if s in m:m[s] += 1else:m[s] = 1cnt = 0for i in range(0, n):for j in range(0, n):visited_vlaue = 0 - (nums3[i] + nums4[j])if visited_vlaue in m:cnt += m[visited_vlaue]return cnt

四、字符串

4.1 反轉(zhuǎn)字符串

題目：leetcode 344

思路：兩個(gè)指針往中間走，交換位置元素即可

class Solution(object):def reverseString(self, s):""":type s: List[str]:rtype: None Do not return anything, modify s in-place instead."""i = 0j = len(s) - 1while i < j:tmp = s[i]s[i] = s[j]s[j] = tmpi += 1j -= 1

4.2 反轉(zhuǎn)字符串II

題目：leetcode 541

思路：使用range，步長(zhǎng)為2k，然后取每個(gè)步長(zhǎng)的k個(gè)字符來(lái)進(jìn)行反轉(zhuǎn)即可

class Solution(object):def reverse_sub(self, sub):i = 0j = len(sub) - 1while i < j:tmp = sub[i]sub[i] = sub[j]sub[j] = tmpi += 1j -= 1return subdef reverseStr(self, s, k):""":type s: str:type k: int:rtype: str"""res = list(s)for i in range(0, len(res), 2*k):res[i:i+k] = self.reverse_sub(res[i:i+k])return "".join(res)    

4.3 反轉(zhuǎn)字符串里的單詞

題目：leetcode 151

思路：使用split函數(shù)分割然后交換元素即可

class Solution(object):def reverseWords(self, s):""":type s: str:rtype: str"""l = s.split(" ")res = list()j = len(l) - 1while j >= 0:if l[j] != "":res.append(l[j])j -= 1return " ".join(res)在Python 2中，字符串的 split() 方法用于將字符串拆分成一個(gè)列表。如果你不提供任何參數(shù)，split() 方法會(huì)將字符串按空白字符（空格、制表符、換行符等）進(jìn)行拆分，并自動(dòng)去除字符串兩端的空白字符和多余的空白字符。
class Solution:def reverseWords(self, s: str) -> str:# 將字符串拆分為單詞，即轉(zhuǎn)換成列表類型words = s.split()# 反轉(zhuǎn)單詞left, right = 0, len(words) - 1while left < right:words[left], words[right] = words[right], words[left]left += 1right -= 1# 將列表轉(zhuǎn)換成字符串return " ".join(words)

五、棧和隊(duì)列

5.1 用棧實(shí)現(xiàn)隊(duì)列

題目：leetcode 232

思路：

class MyQueue(object):def __init__(self):self.stack_in = []self.stack_out = []def push(self, x):""":type x: int:rtype: None有元素就直接往輸入棧添加，輸入棧會(huì)把輸入順序顛倒"""self.stack_in.append(x)def pop(self):""":rtype: int輸出棧為空時(shí)，把輸入棧的元素往輸出棧倒進(jìn)去，負(fù)負(fù)得正，取最后的元素并刪掉"""if len(self.stack_out) < 1:while self.stack_in:self.stack_out.append(self.stack_in.pop())return self.stack_out.pop()def peek(self):""":rtype: int輸出棧為空時(shí)，把輸入棧的元素往輸出棧倒進(jìn)去，負(fù)負(fù)得正，取最后的元素不需要?jiǎng)h除"""if len(self.stack_out) < 1:while self.stack_in:self.stack_out.append(self.stack_in.pop())return self.stack_out[-1]def empty(self):""":rtype: bool輸入?；蜉敵鰲６紴榭?#xff0c;則隊(duì)列為空"""return len(self.stack_out) < 1 and len(self.stack_in) < 1# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

5.2 用隊(duì)列實(shí)現(xiàn)棧

題目：leetcode 225

思路：

from collections import deque
class MyStack(object):def __init__(self):self.queue1 = deque()self.queue2 = deque()def push(self, x):""":type x: int:rtype: None"""self.queue1.append(x)while self.queue2:self.queue1.append(self.queue2.popleft())self.queue1, self.queue2 = self.queue2, self.queue1def pop(self):""":rtype: int"""return self.queue2.popleft()def top(self):""":rtype: int"""return self.queue2[0]def empty(self):""":rtype: bool"""return not self.queue2# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

5.3 有效的括號(hào)

題目：leetcode 20

思路：遍歷字符串，每遇到一個(gè)左括號(hào)，就填一個(gè)右括號(hào)進(jìn)入棧中，遍歷到右括號(hào)時(shí)，看是否相等，相等就pop右括號(hào)出來(lái)；最后如果右括號(hào)和最后一個(gè)元素不相等或者棧為空，那么說(shuō)明括號(hào)不是有效的

class Solution(object):def isValid(self, s):""":type s: str:rtype: bool"""stack = []for item in s:if item == '(':stack.append(')')elif item == '[':stack.append(']')elif item == '{':stack.append('}')elif len(stack) < 1 or item != stack[-1]:return Falseelse:stack.pop()return True

5.4 刪除字符串中所有的相鄰重復(fù)項(xiàng)

題目：leetcode 1047

思路：遍歷字符串，棧中存放遍歷過(guò)的元素，如果棧不為空且最后一個(gè)元素和當(dāng)前元素相等，那么pop；否則遍歷放元素進(jìn)去即可

class Solution(object):def removeDuplicates(self, s):""":type s: str:rtype: str"""stack = []for item in s:if stack and stack[-1] == item:stack.pop()else:stack.append(item)return "".join(stack)

5.5 逆波蘭表達(dá)式求值

題目：leetcode 150

思路：碰到數(shù)字就放到棧里，否則碰到運(yùn)算符時(shí)，從棧中取兩個(gè)元素做對(duì)應(yīng)運(yùn)算，把結(jié)果放到棧里即可

class Solution(object):def evalRPN(self, tokens):""":type tokens: List[str]:rtype: int"""stack = []for item in tokens:if item in ["+", "-", "*", "/"]:t1 = stack.pop()t2 = stack.pop()t = 0if item == "+":t = t1 + t2elif item == "-":t = t2 - t1elif item == "*":t = t1 * t2elif item == "/":t = t2 / t1 if t2 * t1 > 0 else -(abs(t2) // abs(t1))stack.append(t)else:stack.append(int(item))return stack.pop()

5.6 滑動(dòng)窗口最大值

題目：leetcode 239

思路：構(gòu)造單調(diào)隊(duì)列，維護(hù)有可能成為窗口里最大值的元素，同時(shí)保證隊(duì)列里的元素是從大到小的

from collections import dequeclass MyQueue(object):def __init__(self):"""這個(gè)梯隊(duì)第一個(gè)元素永遠(yuǎn)是梯隊(duì)里能力最大的，后面進(jìn)來(lái)的元素都比這個(gè)隊(duì)首小"""self.queue = deque()def queue_push(self, value):"""壓入元素時(shí)，踢掉梯隊(duì)尾部比這個(gè)新人能力差的老人"""while self.queue and value > self.queue[-1]:self.queue.pop()self.queue.append(value)def queue_pop(self, value):"""彈出元素時(shí)(窗口滑動(dòng)，梯隊(duì)前面的人要走了)，重新調(diào)整梯隊(duì)，保證梯隊(duì)里第一個(gè)元素是最大的"""if self.queue and value == self.queue[0]:self.queue.popleft()def get_max_in_queue(self):"""獲取梯隊(duì)里最厲害的，也就是隊(duì)列第一個(gè)元素"""return self.queue[0]class Solution(object):def maxSlidingWindow(self, nums, k):q = MyQueue()result = []for i in range(0, k):q.queue_push(nums[i])result.append(q.get_max_in_queue())for i in range(k, len(nums)):q.queue_pop(nums[i-k]) # 窗口滑動(dòng)過(guò)程中，移除窗口左側(cè)的元素q.queue_push(nums[i])result.append(q.get_max_in_queue())return result

5.7 前k個(gè)高頻元素

題目：leetcode 347

思路：堆是一個(gè)完全二叉樹，樹中每個(gè)節(jié)點(diǎn)的值都不小于/不大于其左右孩子的值。大頂堆每次加元素進(jìn)來(lái)時(shí)，彈出的是大元素，最后留下最小的幾個(gè)元素；小頂堆每次加元素進(jìn)來(lái)時(shí)，彈出的是堆頂?shù)男≡?#xff0c;最后留下最大的幾個(gè)元素。

import heapqdata = [3, 1, 4, 1, 5, 9, 2, 6, 5]
# 將可迭代對(duì)象轉(zhuǎn)換為堆數(shù)據(jù)結(jié)構(gòu)
heapq.heapify(data)heap = []
heapq.heappush(heap, 3)
# 默認(rèn)小頂堆
min_element = heapq.heappop(heap)# 創(chuàng)建小頂堆
min_heap = [3, 1, 4, 1, 5, 9, 2, 6, 5]
heapq.heapify(min_heap)
print(min_heap)  # 輸出: [1, 1, 2, 3, 5, 9, 4, 6, 5]# 創(chuàng)建大頂堆，取兩次反，第一次原來(lái)小值變大值，大值變小值，得到一個(gè)臨時(shí)小頂堆。第二次是把它變回原來(lái)的值
max_heap = [-x for x in min_heap]
heapq.heapify(max_heap)
max_heap = [-x for x in max_heap]
print(max_heap)  # 輸出: [9, 6, 5, 5, 3, 4, 2, 1, 1]# push元組時(shí)，按第一個(gè)元素排序
>>> s = [(1, "a"), (3, "c"), (2, "b")]
>>> heapq.heapify(s)
>>> s
[(1, 'a'), (3, 'c'), (2, 'b')]>>> heapq.heappop(s)
(1, 'a')
>>> heapq.heappop(s)
(2, 'b')
>>> heapq.heappop(s)
(3, 'c')

import heapq
class Solution(object):def topKFrequent(self, nums, k):m = dict()for i in range(0, len(nums)):m[nums[i]] = m.get(nums[i], 0) + 1min_heap = []for key, freq in m.items():heapq.heappush(min_heap, (freq, key))# 如果堆的大小大于了K，則隊(duì)列彈出，保證堆的大小一直為kif len(min_heap) > k:heapq.heappop(min_heap)ret = []for i in range(0, k):ret.append(heapq.heappop(min_heap)[1])return ret

六、二叉樹

6.1 二叉樹種類

1、滿二叉樹：一棵二叉樹只有度為0和度為2的節(jié)點(diǎn)，且度為0的節(jié)點(diǎn)在同一層上

• 深度為k，有2^k-1個(gè)節(jié)點(diǎn)

2、完全二叉樹：一棵二叉樹除了底層節(jié)點(diǎn)沒填滿，其余每層節(jié)點(diǎn)數(shù)都達(dá)到最大值，且最下面一層的節(jié)點(diǎn)都集中在該層最左邊的若干位置

• 如果最底層為h層，則該層包含1-2^(h-1)個(gè)節(jié)點(diǎn)
• 堆是一個(gè)完全二叉樹，同時(shí)保證父子節(jié)點(diǎn)的順序關(guān)系

3、二叉搜索樹：節(jié)點(diǎn)上有值的有序樹

• 如果它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值小于它根節(jié)點(diǎn)的值
• 如果它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值大于它根節(jié)點(diǎn)的值
• 它的左右子樹分別稱為二叉排序樹

4、平衡二叉搜索樹（AVL）：空樹或它的左右兩個(gè)子樹高度差不超過(guò)1，左右兩個(gè)子樹都是平衡二叉樹

6.2 二叉樹的存儲(chǔ)

二叉樹可以鏈?zhǔn)酱鎯?chǔ)，也可以順序存儲(chǔ)

• 鏈?zhǔn)酱鎯?chǔ)：使用指針，把分布在各個(gè)地址的節(jié)點(diǎn)串聯(lián)
• 順序存儲(chǔ)：使用數(shù)組，存儲(chǔ)的元素在內(nèi)存是連續(xù)分布的。如果父節(jié)點(diǎn)的數(shù)組下標(biāo)是i，左孩子是2*i+1，右孩子是2*i+2

6.3 二叉樹的遍歷

兩種遍歷方式：

• 深度優(yōu)先遍歷：先往深走，遇到葉子節(jié)點(diǎn)再往回走。包括前序（中左右）、中序（左中右）、后序（左右中）遍歷（

  前中后序指的就是中間節(jié)點(diǎn)的位置），一般使借助棧使用遞歸來(lái)實(shí)現(xiàn)

• 廣度優(yōu)先遍歷：一層一層遍歷。包括層序遍歷，一般使用隊(duì)列來(lái)實(shí)現(xiàn)

1、前序遍歷

題目：leetcode 144

迭代法：使用棧來(lái)模擬遞歸，前序遍歷是中左右，先將根節(jié)點(diǎn)入棧，然后右、左；保證出棧時(shí)處理時(shí)放到數(shù)組的元素順序是中左右

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def preorderTraversal(self, root):""":type root: Optional[TreeNode]:rtype: List[int]"""if not root:return []ret = []stack = [root]while len(stack) > 0:item = stack.pop()ret.append(item.val)if item.right:stack.append(item.right)if item.left:stack.append(item.left)return ret

遞歸法：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def traversal(self, root, res):if not root:returnres.append(root.val)self.traversal(root.left, res)self.traversal(root.right, res)def preorderTraversal(self, root):""":type root: Optional[TreeNode]:rtype: List[int]"""res = list()self.traversal(root, res)return res

2、后序遍歷

題目：leetcode 145

迭代法：在后序遍歷時(shí)，我們希望得到左右中的順序，翻轉(zhuǎn)后得到中右左，也就是我們的處理順序應(yīng)該是中右左

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def postorderTraversal(self, root):""":type root: Optional[TreeNode]:rtype: List[int]"""if not root:return []ret = []stack = [root]while len(stack) > 0:node = stack.pop()ret.append(node.val)if node.left:stack.append(node.left)if node.right:stack.append(node.right)# 可以直接result[::-1]i = 0j = len(ret) - 1while i < j:ret[i], ret[j] = ret[j], ret[i]i += 1j -= 1return ret

遞歸法：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def traversal(self, root, res):if not root:returnself.traversal(root.left, res)self.traversal(root.right, res)res.append(root.val)def postorderTraversal(self, root):""":type root: Optional[TreeNode]:rtype: List[int]"""res = list()self.traversal(root, res)return res

3、中序遍歷

題目：leetcode 94

迭代法：前序遍歷和后續(xù)遍歷中，要訪問(wèn)的元素和要處理的元素是一致的。而中序遍歷是左中右，先訪問(wèn)的是二叉樹頂部節(jié)點(diǎn)，然后一層層下去直到到達(dá)左子樹的最底部，再開始處理節(jié)點(diǎn)（放到result數(shù)組中），所以訪問(wèn)順序和處理順序是不一樣的。所以在中序遍歷的迭代寫法中，需要用指針遍歷來(lái)幫助訪問(wèn)節(jié)點(diǎn)，棧則用來(lái)處理節(jié)點(diǎn)上的元素

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def inorderTraversal(self, root):""":type root: Optional[TreeNode]:rtype: List[int]"""res = list()stack = list() # 不能提前把根節(jié)點(diǎn)加到棧中，要先找到左子樹最底部cur = rootwhile cur or len(stack) > 0:if cur:stack.append(cur)cur = cur.leftelse:cur = stack.pop()res.append(cur.val)cur = cur.rightreturn res

遞歸法：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def inorderTraversal(self, root):""":type root: Optional[TreeNode]:rtype: List[int]"""res = list()def dfs(root):if root is None:returndfs(root.left)res.append(root.val)dfs(root.right)	dfs(root)return res

4、層序遍歷

題目：leetcode 102

迭代法：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
class Solution(object):def levelOrder(self, root):""":type root: Optional[TreeNode]:rtype: List[List[int]]"""if not root:return []result = []my_queue = deque()my_queue.append(root)while my_queue:level_nodes = []# 每層元素先進(jìn)先出for _ in range(0, len(my_queue)):cur = my_queue.popleft()level_nodes.append(cur.val)if cur.left:my_queue.append(cur.left)if cur.right:my_queue.append(cur.right)result.append(level_nodes)return result

遞歸法：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def levelOrder(self, root):""":type root: Optional[TreeNode]:rtype: List[List[int]]"""if not root:return []level_nodes = []def traversal(root, level):if not root:return # 每到新的一層，加一個(gè)空數(shù)組準(zhǔn)備收集這一層的元素if len(level_nodes) == level:level_nodes.append([])level_nodes[level].append(root.val)traversal(root.left, level+1)traversal(root.right, level+1)traversal(root, 0)return level_nodes

6.4 二叉樹層序遍歷相關(guān)

6.4.1 二叉樹層序遍歷II

題目：leetcode 107

思路：使用隊(duì)列做二叉樹層序遍歷，然后逆序輸出即可

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
class Solution(object):def levelOrderBottom(self, root):""":type root: Optional[TreeNode]:rtype: List[List[int]]"""if not root:return []result = []my_queue = deque()my_queue.append(root)while len(my_queue) > 0:level_nodes = []for _ in range(0, len(my_queue)):cur = my_queue.popleft()level_nodes.append(cur.val)if cur.left:my_queue.append(cur.left)if cur.right:my_queue.append(cur.right)result.append(level_nodes)return result[::-1]

6.4.2 二叉樹的右視圖

題目：leetcode 199

思路：其實(shí)就是層序遍歷，找到每一層的最后一個(gè)節(jié)點(diǎn)即可

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
class Solution(object):def rightSideView(self, root):""":type root: Optional[TreeNode]:rtype: List[int]"""if not root:return []result = []my_queue = deque()my_queue.append(root)while my_queue:level_nodes = []for _ in range(0, len(my_queue)):cur = my_queue.popleft()level_nodes.append(cur.val)if cur.left:my_queue.append(cur.left)if cur.right:my_queue.append(cur.right)result.append(level_nodes[-1])return result

6.4.3 二叉樹的平均值

題目：leetcode 637

思路：層序遍歷

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def averageOfLevels(self, root):""":type root: Optional[TreeNode]:rtype: List[float]"""from collections import dequeret = []level_queue = deque()level_queue.append(root)while level_queue:level_nodes = []for _ in range(0, len(level_queue)):cur = level_queue.popleft()level_nodes.append(cur.val)if cur.left:level_queue.append(cur.left)if cur.right:level_queue.append(cur.right)ret.append(float(sum(level_nodes))/len(level_nodes))return ret

6.4.4 N叉樹的層序遍歷

題目：leetcode 429

思路：層序遍歷，這里children是個(gè)數(shù)組

"""
# Definition for a Node.
class Node(object):def __init__(self, val=None, children=None):self.val = valself.children = children
"""
class Solution(object):def levelOrder(self, root):""":type root: Node:rtype: List[List[int]]"""from collections import dequeret = []level_queue = deque()level_queue.append(root)while level_queue:level_nodes = []for _ in range(0, len(level_queue)):cur = level_queue.popleft()level_nodes.append(cur.val)for idx in range(0, len(cur.children)):level_queue.append(cur.children[idx])ret.append(level_nodes)return ret

6.4.5 在每個(gè)樹行中找最大值

題目：leetcode 515

思路：層序遍歷

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def largestValues(self, root):""":type root: Optional[TreeNode]:rtype: List[int]"""from collections import dequeret = []level_queue = deque()level_queue.append(root)while level_queue:level_nodes = []for _ in range(0, len(level_queue)):cur = level_queue.popleft()level_nodes.append(cur.val)if cur.left:level_queue.append(cur.left)if cur.right:level_queue.append(cur.right)ret.append(max(level_nodes))return ret

6.4.6 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針

題目：leetcode 116

思路：層序遍歷，遍歷每一層所有節(jié)點(diǎn)之前，維護(hù)一個(gè)prev記錄這一層所有節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，如果有這個(gè)prev，那么就把prev的next指向當(dāng)前節(jié)點(diǎn)，然后更新prev

"""
# Definition for a Node.
class Node(object):def __init__(self, val=0, left=None, right=None, next=None):self.val = valself.left = leftself.right = rightself.next = next
"""class Solution(object):def connect(self, root):""":type root: Node:rtype: Node"""if not root:return rootfrom collections import dequelevel_queue = deque()level_queue.append(root)while level_queue:prev = Nonefor _ in range(0, len(level_queue)):cur = level_queue.popleft()if prev:prev.next = curprev = curif cur.left:level_queue.append(cur.left)if cur.right:level_queue.append(cur.right)return root

6.4.7 二叉樹的最大深度

題目：leetcode 104

思路：層序遍歷

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def maxDepth(self, root):""":type root: Optional[TreeNode]:rtype: int"""if not root:return 0from collections import dequedeep = 0level_queue = deque()level_queue.append(root)while level_queue:deep += 1for _ in range(0, len(level_queue)):cur = level_queue.popleft()if cur.left:level_queue.append(cur.left)if cur.right:level_queue.append(cur.right)return deep

6.4.8 二叉樹的最小深度

題目：leetcode 111

思路：層序遍歷，因?yàn)槭菑纳系较卤闅v，遍歷到當(dāng)前節(jié)點(diǎn)既沒有左子樹也沒有右子樹時(shí)，說(shuō)明到了高度的最低點(diǎn)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def minDepth(self, root):""":type root: Optional[TreeNode]:rtype: int"""if not root:return 0from collections import dequedeep = 0level_queue = deque()level_queue.append(root)while level_queue:deep += 1for _ in range(0, len(level_queue)):cur = level_queue.popleft()if cur.left:level_queue.append(cur.left)if cur.right:level_queue.append(cur.right)if cur.left is None and cur.right is None:return deepreturn deep

6.5 翻轉(zhuǎn)二叉樹

題目：leetcode 226

思路：

1、遞歸

• 終止條件：節(jié)點(diǎn)為空則返回
• 單層邏輯：交換左右節(jié)點(diǎn)，然后翻轉(zhuǎn)左子樹、再翻轉(zhuǎn)右子樹，翻完了返回根節(jié)點(diǎn)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def invertTree(self, root):""":type root: Optional[TreeNode]:rtype: Optional[TreeNode]"""if not root:return roottmp = root.leftroot.left = root.rightroot.right = tmpself.invertTree(root.left)self.invertTree(root.right)return root

2、迭代法

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def invertTree(self, root):""":type root: Optional[TreeNode]:rtype: Optional[TreeNode]"""if not root:return rootstack = [root]while stack:cur = stack.pop()cur.left, cur.right = cur.right, cur.leftif cur.left:stack.append(cur.left)if cur.right:stack.append(cur.right)return root

3、層序遍歷

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def invertTree(self, root):""":type root: Optional[TreeNode]:rtype: Optional[TreeNode]"""if not root:return rootfrom collections import dequemy_queue = deque()my_queue.append(root)while my_queue:for _ in range(0, len(my_queue)):node = my_queue.popleft()node.left, node.right = node.right, node.leftif node.left:my_queue.append(node.left)if node.right:my_queue.append(node.right)return root

6.6 對(duì)稱二叉樹

題目：leetcode 101

思路：比較左子樹和右子樹是不是互相翻轉(zhuǎn)的，即是要比較兩棵樹。只能是后序遍歷，一棵樹遍歷順序是左右中，另一棵樹遍歷順序是右左中

遞歸法：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):"""要比較的是根節(jié)點(diǎn)的兩個(gè)子樹是否是相互翻轉(zhuǎn)，所以要比較的是兩個(gè)樹，參數(shù)是左子樹節(jié)點(diǎn)和右子樹根節(jié)點(diǎn)，返回值是bool	"""def compare(self, left, right):if left is None and right:return Falseelif right is None and left:return Falseelif left is None and right is None:return Trueelif left.val != right.val:return Falseelse:outside = self.compare(left.left, right.right)inside = self.compare(left.right, right.left)return outside and insidedef isSymmetric(self, root):""":type root: Optional[TreeNode]:rtype: bool"""if not root:return Truereturn self.compare(root.left, root.right)

迭代法：類似層序遍歷，每一層遍歷按左節(jié)點(diǎn)左孩子，右節(jié)點(diǎn)右孩子，左節(jié)點(diǎn)右孩子，右節(jié)點(diǎn)左孩子入隊(duì)列

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def isSymmetric(self, root):""":type root: Optional[TreeNode]:rtype: bool"""if not root:return Truefrom collections import dequemy_queue = deque()my_queue.append(root.left)my_queue.append(root.right)while my_queue:left_node = my_queue.popleft()right_node = my_queue.popleft()if left_node is None and right_node is None:continueif left_node.left is None and right_node.right:return Falseelif left_node.right is None and right_node.left:return Falseelif left_node is None and right_node is None:return Trueelse:my_queue.append(left_node.left)my_queue.append(right_node.right)my_queue.append(left_node.right)my_queue.append(right_node.left)return True

6.7 相同的樹

題目：leetcode 100

思路：遞歸，輸入兩棵樹，設(shè)定相同的條件，按順序比較兩棵樹即可

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def compare(self, left, right):if left is None and right:return Falseelif right is None and left:return Falseelif left is None and right is None:return Trueelif left.val != right.val:return Falseelse:left_compare = self.compare(left.left, right.left)right_compare = self.compare(left.right, right.right)return left_compare and right_comparedef isSameTree(self, p, q):""":type p: Optional[TreeNode]:type q: Optional[TreeNode]:rtype: bool"""return self.compare(p, q)

6.8 另一個(gè)樹的子樹

題目：leetcode 572

思路：層序遍歷每個(gè)大樹的節(jié)點(diǎn)，判斷每個(gè)節(jié)點(diǎn)是否和另一個(gè)樹是子樹關(guān)系即可

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def compare(self, left, right):if left and right is None:return Falseelif right and left is None:return Falseelif left is None and right is None:return Trueelse:left_same = self.compare(left.left, right.left)right_same = self.compare(left.right, right.right)return left_same and right_samedef isSubtree(self, root, subRoot):""":type root: Optional[TreeNode]:type subRoot: Optional[TreeNode]:rtype: bool"""if not root:return Falsefrom collections import dequemy_queue = deque()my_queue.append(root)while my_queue:for _ in range(0, len(my_queue)):node = my_queue.popleft()if self.compare(node, subRoot):return Trueif node.left:my_queue.append(node.left)if node.right:my_queue.append(node.right)return False

6.9 二叉樹的最小深度

題目：leetcode 111

思路：最小深度是指從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)（左右都為空的節(jié)點(diǎn)）的最短路徑上的節(jié)點(diǎn)數(shù)量

遞歸法，分別求左右子樹高度，在有一只子樹的情況下+1，否則就是左右都為空了要取左右之中的最小值

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def get_depth(self, root):if not root:return 0h_left = self.get_depth(root.left)h_right = self.get_depth(root.right)if root.left and root.right is None:return 1 + h_leftif root.right and root.left is None:return 1 + h_rightreturn 1 + min(self.get_depth(root.left), self.get_depth(root.right))def minDepth(self, root):""":type root: Optional[TreeNode]:rtype: int"""return self.get_depth(root)

迭代法：層序遍歷記錄高度，當(dāng)碰到左右子樹都為空的節(jié)點(diǎn)，返回此時(shí)的高度即可

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def minDepth(self, root):""":type root: Optional[TreeNode]:rtype: int"""if not root:return 0from collections import dequemy_queue = deque()my_queue.append(root)depth = 0while my_queue:depth += 1for _ in range(0, len(my_queue)):node = my_queue.popleft()if node.left:my_queue.append(node.left)if node.right:my_queue.append(node.right)if not node.left and not node.right:return depthreturn depth

6.10 完全二叉樹的節(jié)點(diǎn)個(gè)數(shù)

題目：leetcode 222

思路：完全二叉樹是指除了最底下一層沒填滿，其他都填滿了的二叉樹

遞歸，分別求左右子樹的節(jié)點(diǎn)個(gè)數(shù)，最后加起來(lái)即可

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def cnt(self, root):if not root:return 0cnt_left = self.cnt(root.left)cnt_right = self.cnt(root.right)return 1 + cnt_left + cnt_rightdef countNodes(self, root):""":type root: Optional[TreeNode]:rtype: int"""return self.cnt(root)

迭代：使用層序遍歷

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def countNodes(self, root):""":type root: Optional[TreeNode]:rtype: int"""if not root:return 0from collections import dequemy_queue = deque()my_queue.append(root)cnt = 0while my_queue:for _ in range(0, len(my_queue)):node = my_queue.popleft()cnt += 1if node.left:my_queue.append(node.left)if node.right:my_queue.append(node.right)return cnt

6.11 平衡二叉樹

題目：leetcode 110

思路：平衡二叉樹的定義是一個(gè)二叉樹每個(gè)節(jié)點(diǎn)的左右兩個(gè)字樹的高度差不超過(guò)1。于是我們可以去求每個(gè)節(jié)點(diǎn)的高度，遞歸過(guò)程中判斷左右子樹的高度差是否超過(guò)1，以及左右子樹是否平衡來(lái)實(shí)現(xiàn)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def get_depth(self, root):if not root:return 0left_depth = self.get_depth(root.left)right_depth = self.get_depth(root.right)return 1 + max(left_depth, right_depth)def isBalancedCore(self, root):if not root:return Trueif abs(self.get_depth(root.left) - self.get_depth(root.right)) > 1:return Falsereturn self.isBalancedCore(root.left) and self.isBalancedCore(root.right)def isBalanced(self, root):""":type root: Optional[TreeNode]:rtype: bool"""return self.isBalancedCore(root)

6.12 二叉樹的所有路徑

題目：leetcode 257

思路：前序遍歷，保證root指向孩子節(jié)點(diǎn)

• 確定終止條件：遞歸過(guò)程中，到葉子節(jié)點(diǎn)就可以停止做收集了，沒必要到空節(jié)點(diǎn)
• 遞歸過(guò)程中要做回溯，path不能一直加入節(jié)點(diǎn)，還要?jiǎng)h節(jié)點(diǎn)，然后才能加入新的節(jié)點(diǎn)，回溯和遞歸是一一對(duì)應(yīng)的，有一個(gè)遞歸，就要有一個(gè)回溯

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def travalsal(self, root, path, result):path.append(root.val)if not root.left and not root.right:result.append("->".join(map(str, path)))returnif root.left:self.travalsal(root.left, path, result)path.pop() # path不能一直加入節(jié)點(diǎn)，還要?jiǎng)h節(jié)點(diǎn)，然后才能加入新的節(jié)點(diǎn)，回溯和遞歸是一一對(duì)應(yīng)的，有一個(gè)遞歸，就要有一個(gè)回溯if root.right:self.travalsal(root.right, path, result)path.pop()def binaryTreePaths(self, root):""":type root: Optional[TreeNode]:rtype: List[str]"""if not root:return []path = []result = []self.travalsal(root, path, result)return result

6.13 左葉子之和

題目：leetcode 404

思路：

• 判斷當(dāng)前節(jié)點(diǎn)是不是左葉子要通過(guò)節(jié)點(diǎn)的父節(jié)點(diǎn)判斷其左孩子是不是左葉子，即如果該節(jié)點(diǎn)的左節(jié)點(diǎn)不為空，該節(jié)點(diǎn)的左節(jié)點(diǎn)的左節(jié)點(diǎn)為空，該節(jié)點(diǎn)的左節(jié)點(diǎn)的右節(jié)點(diǎn)為空，則找到了一個(gè)左葉子
• 遇到左葉子節(jié)點(diǎn)時(shí)，記錄數(shù)值，遞歸分別求左右子樹的左葉子和，相加就是整個(gè)樹的左葉子之和

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def get_left_sum(self, root):if not root:return 0if not root.left and not root.right:return 0left_val = self.get_left_sum(root.left)if root.left and not root.left.left and not root.left.right:left_val = root.left.valright_val = self.get_left_sum(root.right)return left_val + right_valdef sumOfLeftLeaves(self, root):""":type root: Optional[TreeNode]:rtype: int"""if not root:return 0return self.get_left_sum(root)

6.14 找樹左下角的值

題目：leetcode 513

思路：

1、遞歸+回溯

• 找到葉子節(jié)點(diǎn)那一層（也就是深度最大的葉子節(jié)點(diǎn)），然后保證優(yōu)先左邊搜索

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):m_depth = float('-inf')result = 0def travalsal(self, root, depth):# 找到葉子節(jié)點(diǎn)那一層（也就是深度最大的葉子節(jié)點(diǎn)）if not root.left and not root.right:if self.m_depth < depth:self.m_depth = depthself.result = root.valreturnif root.left:depth += 1self.travalsal(root.left, depth)depth -= 1 # 回溯if root.right:depth += 1self.travalsal(root.right, depth)depth -= 1def findBottomLeftValue(self, root):""":type root: Optional[TreeNode]:rtype: int"""if not root:return 0self.travalsal(root, 0)return self.result

2、層序遍歷

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def findBottomLeftValue(self, root):""":type root: Optional[TreeNode]:rtype: int"""if not root:return 0from collections import dequemy_queue = deque()my_queue.append(root)result = root.valwhile my_queue:for idx in range(0, len(my_queue)):node = my_queue.popleft()if idx == 0:result = node.valif node.left:my_queue.append(node.left)if node.right:my_queue.append(node.right)return result

6.15 路徑總和

題目：leetcode 112

思路：遞歸

• 搜索整個(gè)二叉樹其中一條路徑，遞歸就需要返回值來(lái)保證在遇到符合條件的路徑時(shí)及時(shí)返回
• 使用遞減，如果最后sum為0且同時(shí)到了葉子節(jié)點(diǎn)，則找到了目標(biāo)路徑；否則就是沒找到

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def traversal(self, root, target_sum):if not root.left and not root.right:if target_sum == 0:return Truereturn Falseif root.left:target_sum -= root.left.valif self.traversal(root.left, target_sum):return Truetarget_sum += root.left.valif root.right:target_sum -= root.right.valif self.traversal(root.right, target_sum):return Truetarget_sum += root.right.valreturn Falsedef hasPathSum(self, root, targetSum):""":type root: Optional[TreeNode]:type targetSum: int:rtype: bool"""if not root:return False# 搜索進(jìn)去節(jié)點(diǎn)之前，應(yīng)該讓數(shù)已經(jīng)減過(guò)了return self.traversal(root, targetSum - root.val)

6.16 路徑總和2

題目：leetcode 113

思路：遞歸

• 當(dāng)需要搜索整棵二叉樹不止一條路徑，且不需要處理返回值的時(shí)候，遞歸函數(shù)就不需要返回值。思路類似6.15
• 這里需要注意的是，在遞歸過(guò)程中，如果是self.result.append(self.path)，那么 self.result 中的每個(gè)元素都將是對(duì) self.path 的引用。由于 self.path 是一個(gè)可變的列表，在遞歸過(guò)程中，每次修改 self.path 都會(huì)影響到已經(jīng)添加到 self.result 中的路徑。通過(guò)使用 self.path[:]或者list(self.path)，我們創(chuàng)建了 self.path 的一個(gè)副本，這樣每次添加到 self.result 中的路徑都是獨(dú)立的，不會(huì)受到后續(xù)修改 self.path 的影響

class Solution(object):def traversal(self, root, path, target, result):if not root.left and not root.right:if target == 0:result.append(path[:])returnif root.left:target -= root.left.valpath.append(root.left.val)self.traversal(root.left, path, target, result)target += root.left.valpath.pop()if root.right:target -= root.right.valpath.append(root.right.val)self.traversal(root.right, path, target, result)target += root.right.valpath.pop()def pathSum(self, root, targetSum):""":type root: Optional[TreeNode]:type targetSum: int:rtype: List[List[int]]"""if not root:return []result = []self.traversal(root, [root.val], targetSum - root.val, result)return result

6.17 從中序和后序遍歷序列構(gòu)造二叉樹

題目：leetcode 106

思路：從后序數(shù)組的最后一個(gè)元素為切割點(diǎn)切割中序數(shù)組，再由切割后的中序數(shù)組切割后序數(shù)組

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def traversal(self, inorder, postorder):if len(inorder) == 0 or len(postorder) == 0:return Nonemid_node = postorder[-1]mid_node_idx = 0for idx in range(0, len(inorder)):if inorder[idx] == mid_node:mid_node_idx = idxbreakin_left_list = inorder[0:idx]in_right_list = inorder[idx+1:]post_left_list = postorder[0:len(in_left_list)]post_right_list = postorder[len(post_left_list):len(in_right_list)+1]mid = TreeNode(val=mid_node)mid.left = self.traversal(in_left_list, post_left_list)mid.right = self.traversal(in_right_list, post_right_list)return middef buildTree(self, inorder, postorder):""":type inorder: List[int]:type postorder: List[int]:rtype: Optional[TreeNode]"""return self.traversal(inorder, postorder)

6.18 從前序和中序遍歷序列構(gòu)造二叉樹

題目：leetcode 105

思路：先從前序遍歷第一個(gè)節(jié)點(diǎn)作為中序遍歷序列的分割點(diǎn)，然后取出中序遍歷的左右區(qū)間，對(duì)應(yīng)再取出前序遍歷的左右區(qū)間，遞歸即可

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def buildTree(self, preorder, inorder):""":type preorder: List[int]:type inorder: List[int]:rtype: Optional[TreeNode]"""if 0 in [len(preorder), len(inorder)]:return Nonemid_node_val = preorder[0]mid_node_idx = 0for idx in range(0, len(inorder)):if inorder[idx] == mid_node_val:mid_node_idx = idxbreakin_left = inorder[0:mid_node_idx]in_right = inorder[mid_node_idx+1:]pre_left = preorder[1:len(in_left)+1]pre_right = preorder[len(in_left)+1:]mid_node = TreeNode(val=mid_node_val)mid_node.left = self.buildTree(pre_left, in_left)mid_node.right = self.buildTree(pre_right, in_right)return mid_node

6.19 最大二叉樹

題目：leetcode 654

思路：找最大值去分割左右區(qū)間，遞歸即可

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def build_tree(self, nums):if 0 == len(nums):return Nonemax_val = max(nums)mid = TreeNode(val=max_val)mid_idx = 0for idx in range(0, len(nums)):if nums[idx] == max_val:mid_idx = idxbreakl_list = nums[0:mid_idx]r_list = nums[mid_idx+1:]mid.left = self.build_tree(l_list)mid.right = self.build_tree(r_list)return middef constructMaximumBinaryTree(self, nums):""":type nums: List[int]:rtype: Optional[TreeNode]"""return self.build_tree(nums)

6.20 合并二叉樹

題目：leetcode 617

思路：合并兩棵樹，定一個(gè)merge函數(shù)，同時(shí)操作就可以了

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def merge(self, root1, root2):if not root1 and not root2:return Noneif not root1:return TreeNode(val=root2.val, left=None, right=None)if not root2:return TreeNode(val=root1.val, left=None, right=None)node = TreeNode(val=root1.val+root2.val)node.left = self.merge(root1.left, root2.left)node.right = self.merge(root1.right, root2.right)return nodedef mergeTrees(self, root1, root2):""":type root1: Optional[TreeNode]:type root2: Optional[TreeNode]:rtype: Optional[TreeNode]"""return self.merge(root1, root2)

6.21 二叉搜索樹中的搜索

題目：leetcode 700

思路：二叉搜索樹BST是有序的，遞歸時(shí)，如果值與根節(jié)點(diǎn)相等直接返回，如果比根節(jié)點(diǎn)大，那么在右子樹搜索，否則在左子樹搜索

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def search(self, root, val):if not root:return Noneif root.val == val:return rootif val < root.val:return self.search(root.left, val)if val > root.val:return self.search(root.right, val)return Nonedef searchBST(self, root, val):""":type root: Optional[TreeNode]:type val: int:rtype: Optional[TreeNode]"""return self.search(root, val)

6.22 驗(yàn)證二叉搜索樹

題目：leetcode 98

思路：

方案1

• BST中序遍歷是一個(gè)有序數(shù)組，看這個(gè)數(shù)組是否有序

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def __init__(self):self.visited = list()def is_valid_bst(self, root):if not root:return Trueself.is_valid_bst(root.left)self.visited.append(root.val)self.is_valid_bst(root.right)def isValidBST(self, root):""":type root: Optional[TreeNode]:rtype: bool"""self.is_valid_bst(root)for idx in range(1, len(self.visited)):if self.visited[idx] <= self.visited[idx-1]:return Falsereturn True

方案2

• 遍歷過(guò)程中判斷，這里為什么不能root.left.val < root.val < root.right.val，是因?yàn)闆]有判斷整棵子樹所有節(jié)點(diǎn)
• 雙指針，用pre記錄當(dāng)前遍歷的前一個(gè)節(jié)點(diǎn)，跟有序數(shù)組一樣判斷后一個(gè)是不是比前一個(gè)大

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def __init__(self):self.pre = Nonedef is_valid_bst(self, root):if not root:return Truel = self.is_valid_bst(root.left)if self.pre and self.pre.val >= root.val:return Falseself.pre = rootr = self.is_valid_bst(root.right)return l and rdef isValidBST(self, root):""":type root: Optional[TreeNode]:rtype: bool"""return self.is_valid_bst(root)

6.23 二叉搜索樹的最小絕對(duì)差

題目：leetcode 530

思路：BST求最值類的題目，其實(shí)就是在有序數(shù)組上求最值。使用雙指針來(lái)在遍歷過(guò)程中比較前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)即可，最值只可能在這里面產(chǎn)生

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def __init__(self):self.min_diff = float('inf')self.pre = Nonedef traversal(self, root):if not root:returnself.traversal(root.left)if self.pre:self.min_diff = min(self.min_diff, abs(root.val - self.pre.val))self.pre = rootself.traversal(root.right)def getMinimumDifference(self, root):""":type root: Optional[TreeNode]:rtype: int"""self.traversal(root)return self.min_diff

6.24 二叉搜索樹中的眾數(shù)

題目：leetcode 501

思路：

方案1:

• 遍歷，然后用map統(tǒng)計(jì)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def __init__(self):from collections import defaultdictself.m = defaultdict(int)def traversal(self, root):if not root:returnself.traversal(root.left)self.m[root.val] += 1self.traversal(root.right)def findMode(self, root):""":type root: Optional[TreeNode]:rtype: List[int]"""self.traversal(root)result = []max_cnt = max(self.m.values())for val, cnt in self.m.items():if cnt == max_cnt:result.append(val)return result

方案2:

• 中序遍歷，雙指針，用cnt來(lái)統(tǒng)計(jì)單個(gè)元素出現(xiàn)的頻率，用max_count來(lái)維護(hù)樹中出現(xiàn)最多的頻率
• 另外在這里要注意，在遞歸調(diào)用時(shí)，如果要更新和使用pre，需要將pre作為實(shí)例變量，才可以正確更新self.pre的值，所以最好都使用這種方法

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def __init__(self):self.result = list()self.max_cnt = 0self.cnt = 0self.pre = Nonedef traversal(self, root):if not root:returnself.traversal(root.left)if not self.pre:self.cnt = 1elif self.pre.val == root.val:self.cnt += 1else:# 不相等時(shí)，cnt繼續(xù)統(tǒng)計(jì)單一元素出現(xiàn)的頻率self.cnt = 1self.pre = rootif self.cnt == self.max_cnt:self.result.append(root.val)# 當(dāng) cnt==max_cnt 放進(jìn)來(lái)結(jié)果集時(shí)，有可能max_cnt還不是最大的頻率，所以要?jiǎng)討B(tài)更新max_cnt，并把之前不符合要求的結(jié)果清掉if self.cnt > self.max_cnt:self.max_cnt = self.cntself.result = [root.val]self.traversal(root.right)def findMode(self, root):""":type root: Optional[TreeNode]:rtype: List[int]"""self.traversal(root)return self.result

6.25 二叉樹的最近公共祖先

題目：leetcode 236

思路：自底向上遍歷，但平時(shí)都是從上開始遍歷的，這時(shí)就要用到回溯來(lái)把公共祖先傳遞上去，并且要使用后序遍歷（因?yàn)槭亲笥抑?#xff09;。在傳遞向上的過(guò)程中，

• 如果root是p/q中的一個(gè)，那么直接返回，不走下面的遞歸；否則開始后序遍歷
• 如果左子樹返回不為空，則可能出現(xiàn)了p/q；右子樹同理；當(dāng)都不為空，則當(dāng)前這個(gè)點(diǎn)就是最近公共祖先

# 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 traversal(self, root, p, q):if not root:return Noneif root in [p, q]:return rootl = self.traversal(root.left, p, q)r = self.traversal(root.right, p, q)if l and not r:return lelif r and not l:return relif r and l:return rootelse:return Nonedef lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""return self.traversal(root, p, q)

6.26 二叉搜索樹的最近公共祖先

題目：leetcode 235

思路：利用BST的有序特性，

• 如果p和q都比當(dāng)前遍歷的節(jié)點(diǎn)小，那么應(yīng)該向左遍歷，否則應(yīng)該向右遍歷
• 如果當(dāng)前遍歷這個(gè)節(jié)點(diǎn)的值在p和q之間，這個(gè)節(jié)點(diǎn)就是p和q的公共節(jié)點(diǎn)，因?yàn)樵诖朔植媪?#xff0c;所以這個(gè)節(jié)點(diǎn)就是最近的公共祖先

# 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 traversal(self, root, p, q):if not root:return Noneif root.val > p.val and root.val > q.val:left = self.traversal(root.left, p, q)if left:return leftelif root.val < p.val and root.val < q.val:right = self.traversal(root.right, p, q)if right:return rightelse:return rootdef lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""return self.traversal(root, p, q)

6.27 二叉搜索樹中的插入操作

題目：leetcode 701

思路：利用二叉樹的有序特性，值小就往左邊插，值大就往右邊插，最后返回root

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def insertIntoBST(self, root, val):""":type root: Optional[TreeNode]:type val: int:rtype: Optional[TreeNode]"""if not root:return TreeNode(val=val)if root.val > val:root.left = self.insertIntoBST(root.left, val)if root.val < val:root.right = self.insertIntoBST(root.right, val)return root

6.28 刪除二叉搜索樹中的節(jié)點(diǎn)

題目：leetcode 450

思路：嘗試找到這個(gè)節(jié)點(diǎn)，然后刪除它

1、如果沒找到，返回空；下面都是找到了的情況

2、如果刪的是葉子節(jié)點(diǎn)（左為空，右也為空），直接刪除，返回None，當(dāng)前層的左子樹等于下一層遞歸的返回值

3、如果刪的節(jié)點(diǎn)左不空，右為空，把左子樹掛在當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)的左邊

4、如果刪的節(jié)點(diǎn)左為空，右不空，把右子樹掛在當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)的右邊

5、如果刪的節(jié)點(diǎn)左不空，右不空；以右子樹為例，要找到這個(gè)子樹上最小的那個(gè)節(jié)點(diǎn)（右子樹最左側(cè)，用迭代一直往左走），然后把左子樹掛上去，最后回到左為空，右不為空的情況

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def delete(self, root, key):if not root:return Noneif root.val == key:if not root.left and not root.right:return Noneelif root.left and not root.right:return root.leftelif root.right and not root.left:return root.rightelif root.left and root.right:cur = root.rightwhile cur.left:cur = cur.leftcur.left = root.leftreturn root.rightif root.val > key:root.left = self.delete(root.left, key)if root.val < key:root.right = self.delete(root.right, key)return rootdef deleteNode(self, root, key):""":type root: Optional[TreeNode]:type key: int:rtype: Optional[TreeNode]"""return self.delete(root, key)

6.29 修剪二叉搜索樹

題目：leetcode 669

思路：

這里通過(guò)root.val < low or root.val > high然后返回空來(lái)刪除節(jié)點(diǎn)是錯(cuò)誤的，因?yàn)椴荒鼙ＷC其中一個(gè)條件生效時(shí)，它的子樹也都是滿足條件的，這樣子樹會(huì)都被刪除

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def trim(self, root, low, high):if not root:return Noneif root.val < low:# 遞歸右子樹并返回右子樹符合條件的頭節(jié)點(diǎn)return self.trim(root.right, low, high)if root.val > high:return self.trim(root.left, low, high)# 把下一層處理完左/右子樹的結(jié)果賦給root.left/root.rightroot.left = self.trim(root.left, low, high)root.right = self.trim(root.right, low, high)return rootdef trimBST(self, root, low, high):""":type root: Optional[TreeNode]:type low: int:type high: int:rtype: Optional[TreeNode]"""return self.trim(root, low, high)

6.30 構(gòu)造平衡二叉搜索樹

題目：leetcode 108

思路：一定要選取數(shù)組里面中間的節(jié)點(diǎn)，這樣左右區(qū)間的節(jié)點(diǎn)數(shù)量才是相同的，這樣的二叉樹才是平衡的。分割成左右區(qū)間后繼續(xù)去構(gòu)造二叉樹即可

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def traversal(self, nums, l, r):if l > r:return Nonemid = l + (r - l) // 2root = TreeNode(val=nums[mid])root.left = self.traversal(nums, l, mid - 1)root.right = self.traversal(nums, mid + 1, r)return rootdef sortedArrayToBST(self, nums):""":type nums: List[int]:rtype: Optional[TreeNode]"""return self.traversal(nums, 0, len(nums) - 1)

6.31 把二叉搜索樹轉(zhuǎn)換為累加樹

題目：leetcode 538

思路：把左中右變成右中左遍歷。和數(shù)組一樣使用雙指針累加

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def __init__(self):self.pre = 0def traversal(self, root):if not root:returnself.traversal(root.right)root.val += self.preself.pre = root.valself.traversal(root.left)def convertBST(self, root):""":type root: Optional[TreeNode]:rtype: Optional[TreeNode]"""self.traversal(root)return root