当前位置： 首页 > news >正文

九江 网站建站 设计 公司,旅游目的地网站建设的流程,做静态网站的开题报告,做配送平台网站多少钱文章目录 一、数组1.1 二分查找 1.1.1 二分查找 1.1.2 搜索插入位置1.1.3 排序数组中查找元素第一和最后一个位置1.1.4 x的平方根 1.1.5 有效的完全平方数 1.2 快慢指针 1.2.1 移除元素 1.2.2 删除有序数组中的重复项 1.2.3 移动0 1.2.4 比较含退格的字符串 1.2.5 有序数组的平… 文章目录 一、数组1.1 二分查找 1.1.1 二分查找 1.1.2 搜索插入位置1.1.3 排序数组中查找元素第一和最后一个位置1.1.4 x的平方根 1.1.5 有效的完全平方数 1.2 快慢指针 1.2.1 移除元素 1.2.2 删除有序数组中的重复项 1.2.3 移动0 1.2.4 比较含退格的字符串 1.2.5 有序数组的平方 1.3 滑动窗口 1.3.1 长度最小的子数组 1.3.2 水果成篮 1.3.3 最小覆盖字串 1.4 螺旋矩阵 二、链表 2.1 移除链表元素2.2 设计链表 2.3 反转链表2.4 两两交换链表中的节点 2.5 删除链表的倒数第N个节点 2.6 链表相交 2.7 环形链表 三、哈希表 3.1 哈希碰撞3.2 有效的字母异位词3.3 字母异位词分组3.4 找到字符串中所有字母异位词3.5 赎金信3.6 两个数组的交集3.7 快乐数3.8 两数之和 3.9 四数相加II 四、字符串 4.1 反转字符串 4.2 反转字符串II 4.3 反转字符串里的单词 五、栈和队列 5.1 用栈实现队列5.2 用队列实现栈 5.3 有效的括号5.4 删除字符串中所有的相邻重复项5.5 逆波兰表达式求值5.6 滑动窗口最大值5.7 前k个高频元素 六、二叉树 6.1 二叉树种类6.2 二叉树的存储6.3 二叉树的遍历 6.4 二叉树层序遍历相关6.4.1 二叉树层序遍历II6.4.2 二叉树的右视图6.4.3 二叉树的平均值6.4.4 N叉树的层序遍历6.4.5 在每个树行中找最大值6.4.6 填充每个节点的下一个右侧节点指针6.4.7 二叉树的最大深度6.4.8 二叉树的最小深度 6.5 翻转二叉树6.6 对称二叉树6.7 相同的树6.8 另一个树的子树6.9 二叉树的最小深度6.10 完全二叉树的节点个数6.11 平衡二叉树6.12 二叉树的所有路径6.13 左叶子之和6.14 找树左下角的值6.15 路径总和6.16 路径总和26.17 从中序和后序遍历序列构造二叉树6.18 从前序和中序遍历序列构造二叉树6.19 最大二叉树6.20 合并二叉树6.21 二叉搜索树中的搜索6.22 验证二叉搜索树6.23 二叉搜索树的最小绝对差6.24 二叉搜索树中的众数6.25 二叉树的最近公共祖先6.26 二叉搜索树的最近公共祖先6.27 二叉搜索树中的插入操作6.28 删除二叉搜索树中的节点6.29 修剪二叉搜索树6.30 构造平衡二叉搜索树6.31 把二叉搜索树转换为累加树 一、数组 存放在连续内存空间上相同数据类型的集合可以通过下标索引取到对应的数据 1.1 二分查找 二分查找要求数组是有序且没有重复的元素 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 11.1.3 排序数组中查找元素第一和最后一个位置 题目leetcode 34 思路 1、找第一个位置先二分模板然后思考相等以后什么时候要往左找——在mid-1上的元素如果都大于等于target时需要确保mid-1合法说明第一个位置还在左边。否则mid位置就是第一个。找不到就是-1。2、找最后一个位置先二分模板然后思考相等以后什么时候要往右找——在mid1上的元素小于等于target时需要确保mid1合法说明最后一个位置还在右边。否则mid位置就是最后一个。找不到就是-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[mid1] 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 思路最终结果一定是在0到x之间所以可以用二分。比如中间要找的数是k那么左区间满足k平方小于等于x右区间k平方大于x。也就是如果k平方小于等于x那么k有可能是结果所以把区间缩小到右区间。如果k平方大于x那么k不可能是是结果所以把区间缩小到左区间。一直二分直到左右指针相遇返回结果 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 ans1.1.5 有效的完全平方数 题目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 False1.2 快慢指针 1.2.1 移除元素 题目leetcode 27 思路使用快慢指针快指针获取数组元素慢指针获取新数组中需要更新的位置 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 slow1.2.2 删除有序数组中的重复项 题目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 slow1.2.3 移动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 11.2.4 比较含退格的字符串 题目leetcode 844 思路分别记录两个字符串中退格的个数。i、j指针从后往前遍历目的是把退格跳过然后比较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 True1.2.5 有序数组的平方 题目leetcode 977 思路从后往前遍历保证最后的数是最大的中间做元素交换和覆盖即可 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 nums1.3 滑动窗口 1.3.1 长度最小的子数组 题目leetcode 209 思路滑动窗口j表示终止位置i表示起始位置。终止位置不断移动求和当发现其和大于等于目标值时不断移动起始位置另外减少和在这个过程中计算出窗口的最小长度即可。特殊情况是所有加起来都没有大于目标值那么对这种情况返回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 01.3.2 水果成篮 题目leetcode 904 思路这里fruits中的每个元素代表第i棵树上的水果种类而不是种类数。所以只要保证两个篮子里装了两个种类的水果即可。右指针从0开始把水果捡进篮子篮子内只要超过2个就开始去丢最左边的水果丢了之后移动左指针然后计算最大距离即可 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 res1.3.3 最小覆盖字串 题目leetcode 76 思路定义ht存储t中字符的数量{A: 1, B: 1, C: 1}hs存储s中每个cnt记录当前字符的数量。移动窗口过程中加入元素时如果没超过ht中字符的数量说明是一个有效字符把cnt值加1 class Solution(object):def minWindow(self, s, t)::type s: str:type t: str:rtype: strif len(t) len(s):return # hs统计当前窗口中各个字符的数量hs collections.defaultdict(int)ht collections.defaultdict(int)# 统计t中各字符数量到ht中for char in t:ht[char] 1j i 0cnt 0res_sub_str min_length len(s) 1# 移动右边指针for j in range(len(s)):# 往hs添加当前字符hs[s[j]] 1# 如果添加的字符没有超过ht中对应字符的数量那么有效字符1if hs[s[j]] ht[s[j]]:cnt 1# 看是否移动左边指针当hs中对应元素的数量大于ht中对应元素的数量说明是冗余字符需要删去且左指针往前走while i j and hs[s[i]] ht[s[i]]:hs[s[i]] - 1i 1# 当有效字符数和t的长度相同那么更新最小窗口大小并取窗口内的子字符串if cnt len(t):if (j - i 1) min_length:min_length j - i 1res_sub_str s[i:j1]return res_sub_str1.4 螺旋矩阵 题目leetcode 59 思路模拟顺时针画矩阵填充数组。设置偏移量为边界每个区间都是左闭右开循环次数loop应小于n的一半每次loop完应该将起始坐标x和y沿对角线移动。最后如果n是奇数应该在循环结束时将中心元素填充进去此时x和y已经移动到了中心点 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二、链表 链表是通过指针串联在一起的线性结构但在内存中不是连续分布的分配机制取决于os的内存管理。 每个节点由数据域和指针域组成类型有 单链表双链表每个节点有两个指针域分别指向前一个节点和后一个节点循环链表链表首尾相连通常解决约瑟夫环的问题 对比数组插入/删除O(n)查询O(1)链表的时间复杂度为插入/删除O(1)查询O(n) 链表长度不固定适合频繁增删较少查询的场景 class ListNode:def init(self, val, nextNone):self.val valself.next next2.1 移除链表元素 题目leetcode 203 思路有两种方式 直接在原链表进行删除操作其他节点都是通过前一个节点来删除当前节点的头节点没有前一个节点操作比较难统一设置一个虚拟头节点再进行删除操作统一删除操作从链表最前端dummy节点开始判断下一个元素是否和val相同相同则进行删除操作并移动指针否则移动当前指针到下一个元素 常规删除

Definition for singly-linked list.

class ListNode(object):

def init(self, val0, nextNone):

self.val val

self.next next

class Solution(object):def removeElements(self, head, val)::type head: ListNode:type val: int:rtype: ListNodeif head is None:return Nonedummy ListNode(nexthead)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, val0, nextNone):

self.val val

self.next next

class Solution(object):def removeElements(self, head, val)::type head: ListNode:type val: int:rtype: ListNodeif head is None:return Nonehead.next self.removeElements(head.next, val)if head.val val:return head.nextelse:return head2.2 设计链表 题目leetcode 707 思路如代码所示添加和删除都是先找到位置断开原链加上新链 class ListNode(object):def init(self, val0, nextNone):self.val valself.next nextclass MyLinkedList(object):def init(self):self.dummy ListNode()self.size 0def get(self, index):校验index合法性从虚拟头节点的下一个节点开始遍历链表取值即可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节点的下一个节点是头节点即可self.dummy.next ListNode(valval)self.size 1def addAtTail(self, val):遍历到最后一个节点在最后一个节点后面新增一个节点即可cur self.dummywhile cur.next is not None:cur cur.nextcur.next ListNode(valval)self.size 1def addAtIndex(self, index, val):新增节点时遍历到要添加的位置让当前节点的next指向新节点新节点的next是当前节点的nextif index 0 or index self.size:returncur self.dummyfor idx in range(0, index):cur cur.nextcur.next ListNode(valval, nextcur.next)self.size 1def deleteAtIndex(self, index):删除节点时遍历到要删除的位置让当前节点的next指向下下个节点即可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 反转链表

题目leetcode 206 思路减少空间浪费原地反转 方案1:双指针法初始位置pre指针指向空cur指向头节点每次循环保存cur的下一个节点到tmp改变cur的next指向到pre然后移动pre指针移动cur指针直到cur为空时返回pre指针即可

Definition for singly-linked list.

class ListNode(object):

def init(self, val0, nextNone):

self.val val

self.next next

class Solution(object):def reverseList(self, head)::type head: ListNode:rtype: ListNodecur headpre Nonewhile cur:tmp cur.nextcur.next prepre curcur tmpreturn pre方案2:递归法和双指针法一样的思路递归初始pre指针指向空cur指向头节点每次递归保存cur的下一个节点到tmp改变cur的next指向到pre然后移动pre指针移动cur指针直到cur为空时结束递归返回pre即可

Definition for singly-linked list.

class ListNode(object):

def init(self, val0, nextNone):

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 两两交换链表中的节点 题目leetcode 24 方案1: 思路设定头节点当前节点为头节点暂存1、2、3号元素把cur指向22指向11指向3最后cur往前走两步直到cur的next和next、next有一个为空则停止

Definition for singly-linked list.

class ListNode(object):

def init(self, val0, nextNone):

self.val val

self.next next

class Solution(object):def swapPairs(self, head):dummy ListNode(nexthead)cur dummy# 必须有cur的下一个和下下个才能交换否则说明已经交换结束了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: 思路递归不使用头节点pre指向头节点cur指向head.nextnext是head.next.next每次交换pre和cur然后把nxt当作头节点继续交换最后返回cur

Definition for singly-linked list.

class ListNode(object):

def init(self, val0, nextNone):

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 cur2.5 删除链表的倒数第N个节点 题目leetcode 19 思路使用快慢指针快慢指针同时指向dummy虚拟头节点快指针先走走到头了慢指针就可以删了

Definition for singly-linked list.

class ListNode(object):

def init(self, val0, nextNone):

self.val val

self.next next

class Solution(object):def removeNthFromEnd(self, head, n):dummy ListNode(nexthead)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 思路先尾对齐两个链表求长度差让cur A先走对齐以后一起走直到两个指针指向同一个元素即可

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 None2.7 环形链表

题目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: 快慢指针快指针走两步、慢指针走一步相遇则说明链表有环。相遇以后慢指针回头快慢指针一步一步走直到相遇则为环入口

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 三、哈希表

哈希表一般用来快速判断一个元素是否出现在集合里时间复杂度是O(1) 把元素通过哈希函数映射为哈希表上的索引就可以通过索引下标快速定位到该元素数据结构数组、set、map等 当元素的个数大于哈希表的大小时就容易出现哈希碰撞 3.1 哈希碰撞 指两个以上的元素都映射到了同一个位置解决方法拉链法、线性探测法 1、拉链法 发生冲突的元素都存在同一位置的链表上需要我们适当选择哈希表的大小既不会因为数组空而浪费内存也不会因为链表太长而在查找上花太多时间 2、线性探测法 冲突后就向下找一个空位放冲突的元素 3.2 有效的字母异位词 题目leetcode 242 思路使用哈希表来记录每个元素出现的次数 class Solution(object):def isAnagram(self, s, t)::type s: str:type t: str:rtype: boolrecord [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: boolfrom 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 True3.3 字母异位词分组 题目leetcode 49 思路遍历每个元素对每个元素排序放到列表中即可 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 ret3.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:ilen(p)]if self.is_ok(sub, p):ret.append(i)return ret3.5 赎金信 题目leetcode 383 思路记录一个单词出现的次数再遍历另一个单词减去出现的次数如果出现负数说明不能组成 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 True3.6 两个数组的交集 题目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))用数组存两个列表的元素长度取最大元素两个位置的元素相乘看是否为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 ret3.7 快乐数 题目leetcode 202 思路求和时通过模10获取整数每一位上的数字然后除以10更新数字每一轮看求和数是否出现在哈希表中即可判断是否进入死循环 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 两数之和 题目leetcode 1 思路 方法1:使用哈希表存储key是元素value是元素的下标遍历数组每个元素通过做差找到数据下标返回即可 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(i1, len(nums)):if nums[i] nums[j] target:return [i, j]return [0, 0]3.9 四数相加II 题目leetcode 454 思路先去遍历2个数组统计他们所有元素相加的和以及出现的次数放到字典中再去遍历另外两个数组判断0和另外两个数组任意两个元素之和的差值是否在字典中如果在那么获取这个次数叠加。最后返回统计值即可 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: intn 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 反转字符串 题目leetcode 344 思路两个指针往中间走交换位置元素即可 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 - 14.2 反转字符串II 题目leetcode 541 思路使用range步长为2k然后取每个步长的k个字符来进行反转即可 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: strres list(s)for i in range(0, len(res), 2*k):res[i:ik] self.reverse_sub(res[i:ik])return .join(res) 4.3 反转字符串里的单词 题目leetcode 151 思路使用split函数分割然后交换元素即可 class Solution(object):def reverseWords(self, s)::type s: str:rtype: strl s.split( )res list()j len(l) - 1while j 0:if l[j] ! :res.append(l[j])j - 1return .join(res)在Python 2中字符串的 split() 方法用于将字符串拆分成一个列表。如果你不提供任何参数split() 方法会将字符串按空白字符空格、制表符、换行符等进行拆分并自动去除字符串两端的空白字符和多余的空白字符。 class Solution:def reverseWords(self, s: str) - str:# 将字符串拆分为单词即转换成列表类型words s.split()# 反转单词left, right 0, len(words) - 1while left right:words[left], words[right] words[right], words[left]left 1right - 1# 将列表转换成字符串return .join(words)五、栈和队列 5.1 用栈实现队列 题目leetcode 232 思路 class MyQueue(object):def init(self):self.stack_in []self.stack_out []def push(self, x)::type x: int:rtype: None有元素就直接往输入栈添加输入栈会把输入顺序颠倒self.stack_in.append(x)def pop(self)::rtype: int输出栈为空时把输入栈的元素往输出栈倒进去负负得正取最后的元素并删掉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输出栈为空时把输入栈的元素往输出栈倒进去负负得正取最后的元素不需要删除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输入栈或输出栈都为空则队列为空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 用队列实现栈

题目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: Noneself.queue1.append(x)while self.queue2:self.queue1.append(self.queue2.popleft())self.queue1, self.queue2 self.queue2, self.queue1def pop(self)::rtype: intreturn self.queue2.popleft()def top(self)::rtype: intreturn self.queue2[0]def empty(self)::rtype: boolreturn 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 有效的括号

题目leetcode 20 思路遍历字符串每遇到一个左括号就填一个右括号进入栈中遍历到右括号时看是否相等相等就pop右括号出来最后如果右括号和最后一个元素不相等或者栈为空那么说明括号不是有效的 class Solution(object):def isValid(self, s)::type s: str:rtype: boolstack []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 True5.4 删除字符串中所有的相邻重复项 题目leetcode 1047 思路遍历字符串栈中存放遍历过的元素如果栈不为空且最后一个元素和当前元素相等那么pop否则遍历放元素进去即可 class Solution(object):def removeDuplicates(self, s)::type s: str:rtype: strstack []for item in s:if stack and stack[-1] item:stack.pop()else:stack.append(item)return .join(stack)5.5 逆波兰表达式求值 题目leetcode 150 思路碰到数字就放到栈里否则碰到运算符时从栈中取两个元素做对应运算把结果放到栈里即可 class Solution(object):def evalRPN(self, tokens)::type tokens: List[str]:rtype: intstack []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 滑动窗口最大值 题目leetcode 239 思路构造单调队列维护有可能成为窗口里最大值的元素同时保证队列里的元素是从大到小的 from collections import dequeclass MyQueue(object):def init(self):这个梯队第一个元素永远是梯队里能力最大的后面进来的元素都比这个队首小self.queue deque()def queue_push(self, value):压入元素时踢掉梯队尾部比这个新人能力差的老人while self.queue and value self.queue[-1]:self.queue.pop()self.queue.append(value)def queue_pop(self, value):弹出元素时(窗口滑动梯队前面的人要走了)重新调整梯队保证梯队里第一个元素是最大的if self.queue and value self.queue[0]:self.queue.popleft()def get_max_in_queue(self):获取梯队里最厉害的也就是队列第一个元素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]) # 窗口滑动过程中移除窗口左侧的元素q.queue_push(nums[i])result.append(q.get_max_in_queue())return result 5.7 前k个高频元素 题目leetcode 347 思路堆是一个完全二叉树树中每个节点的值都不小于/不大于其左右孩子的值。大顶堆每次加元素进来时弹出的是大元素最后留下最小的几个元素小顶堆每次加元素进来时弹出的是堆顶的小元素最后留下最大的几个元素。 import heapqdata [3, 1, 4, 1, 5, 9, 2, 6, 5]

将可迭代对象转换为堆数据结构

heapq.heapify(data)heap [] heapq.heappush(heap, 3)

默认小顶堆

min_element heapq.heappop(heap)# 创建小顶堆 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]# 创建大顶堆取两次反第一次原来小值变大值大值变小值得到一个临时小顶堆。第二次是把它变回原来的值 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元组时按第一个元素排序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则队列弹出保证堆的大小一直为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的节点且度为0的节点在同一层上 深度为k有2^k-1个节点 2、完全二叉树一棵二叉树除了底层节点没填满其余每层节点数都达到最大值且最下面一层的节点都集中在该层最左边的若干位置 如果最底层为h层则该层包含1-2^(h-1)个节点堆是一个完全二叉树同时保证父子节点的顺序关系 3、二叉搜索树节点上有值的有序树 如果它的左子树不为空则左子树上所有节点的值小于它根节点的值如果它的右子树不为空则右子树上所有节点的值大于它根节点的值它的左右子树分别称为二叉排序树 4、平衡二叉搜索树AVL空树或它的左右两个子树高度差不超过1左右两个子树都是平衡二叉树 6.2 二叉树的存储 二叉树可以链式存储也可以顺序存储 链式存储使用指针把分布在各个地址的节点串联顺序存储使用数组存储的元素在内存是连续分布的。如果父节点的数组下标是i左孩子是2*i1右孩子是2*i2 6.3 二叉树的遍历 两种遍历方式 深度优先遍历先往深走遇到叶子节点再往回走。包括前序中左右、中序左中右、后序左右中遍历 前中后序指的就是中间节点的位置一般使借助栈使用递归来实现 广度优先遍历一层一层遍历。包括层序遍历一般使用队列来实现
1、前序遍历 题目leetcode 144 迭代法使用栈来模拟递归前序遍历是中左右先将根节点入栈然后右、左保证出栈时处理时放到数组的元素顺序是中左右

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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, val0, leftNone, rightNone):

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 迭代法在后序遍历时我们希望得到左右中的顺序翻转后得到中右左也就是我们的处理顺序应该是中右左

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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, val0, leftNone, rightNone):

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 迭代法前序遍历和后续遍历中要访问的元素和要处理的元素是一致的。而中序遍历是左中右先访问的是二叉树顶部节点然后一层层下去直到到达左子树的最底部再开始处理节点放到result数组中所以访问顺序和处理顺序是不一样的。所以在中序遍历的迭代写法中需要用指针遍历来帮助访问节点栈则用来处理节点上的元素

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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() # 不能提前把根节点加到栈中要先找到左子树最底部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, val0, leftNone, rightNone):

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, val0, leftNone, rightNone):

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 []# 每层元素先进先出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, val0, leftNone, rightNone):

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 # 每到新的一层加一个空数组准备收集这一层的元素if len(level_nodes) level:level_nodes.append([])level_nodes[level].append(root.val)traversal(root.left, level1)traversal(root.right, level1)traversal(root, 0)return level_nodes6.4 二叉树层序遍历相关 6.4.1 二叉树层序遍历II 题目leetcode 107 思路使用队列做二叉树层序遍历然后逆序输出即可

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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 思路其实就是层序遍历找到每一层的最后一个节点即可

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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, val0, leftNone, rightNone):

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 ret6.4.4 N叉树的层序遍历 题目leetcode 429 思路层序遍历这里children是个数组 # Definition for a Node. class Node(object):def init(self, valNone, childrenNone):self.val valself.children childrenclass 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 在每个树行中找最大值 题目leetcode 515 思路层序遍历

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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 ret6.4.6 填充每个节点的下一个右侧节点指针 题目leetcode 116 思路层序遍历遍历每一层所有节点之前维护一个prev记录这一层所有节点的前一个节点如果有这个prev那么就把prev的next指向当前节点然后更新prev # Definition for a Node. class Node(object):def init(self, val0, leftNone, rightNone, nextNone):self.val valself.left leftself.right rightself.next next class Solution(object):def connect(self, root)::type root: Node:rtype: Nodeif 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, val0, leftNone, rightNone):

self.val val

self.left left

self.right right

class Solution(object):def maxDepth(self, root)::type root: Optional[TreeNode]:rtype: intif 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 思路层序遍历因为是从上到下遍历遍历到当前节点既没有左子树也没有右子树时说明到了高度的最低点

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

self.val val

self.left left

self.right right

class Solution(object):def minDepth(self, root)::type root: Optional[TreeNode]:rtype: intif 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 deep6.5 翻转二叉树 题目leetcode 226 思路 1、递归 终止条件节点为空则返回单层逻辑交换左右节点然后翻转左子树、再翻转右子树翻完了返回根节点

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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, val0, leftNone, rightNone):

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 root3、层序遍历

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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 root6.6 对称二叉树 题目leetcode 101 思路比较左子树和右子树是不是互相翻转的即是要比较两棵树。只能是后序遍历一棵树遍历顺序是左右中另一棵树遍历顺序是右左中 递归法

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

self.val val

self.left left

self.right right

class Solution(object):要比较的是根节点的两个子树是否是相互翻转所以要比较的是两个树参数是左子树节点和右子树根节点返回值是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: boolif not root:return Truereturn self.compare(root.left, root.right) 迭代法类似层序遍历每一层遍历按左节点左孩子右节点右孩子左节点右孩子右节点左孩子入队列

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

self.val val

self.left left

self.right right

class Solution(object):def isSymmetric(self, root)::type root: Optional[TreeNode]:rtype: boolif 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 思路递归输入两棵树设定相同的条件按顺序比较两棵树即可

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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: boolreturn self.compare(p, q)6.8 另一个树的子树 题目leetcode 572 思路层序遍历每个大树的节点判断每个节点是否和另一个树是子树关系即可

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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: boolif 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 思路最小深度是指从根节点到最近叶子节点左右都为空的节点的最短路径上的节点数量 递归法分别求左右子树高度在有一只子树的情况下1否则就是左右都为空了要取左右之中的最小值

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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: intreturn self.get_depth(root)迭代法层序遍历记录高度当碰到左右子树都为空的节点返回此时的高度即可

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

self.val val

self.left left

self.right right

class Solution(object):def minDepth(self, root)::type root: Optional[TreeNode]:rtype: intif 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 depth6.10 完全二叉树的节点个数 题目leetcode 222 思路完全二叉树是指除了最底下一层没填满其他都填满了的二叉树 递归分别求左右子树的节点个数最后加起来即可

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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: intreturn self.cnt(root) 迭代使用层序遍历

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

self.val val

self.left left

self.right right

class Solution(object):def countNodes(self, root)::type root: Optional[TreeNode]:rtype: intif 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 cnt6.11 平衡二叉树 题目leetcode 110 思路平衡二叉树的定义是一个二叉树每个节点的左右两个字树的高度差不超过1。于是我们可以去求每个节点的高度递归过程中判断左右子树的高度差是否超过1以及左右子树是否平衡来实现

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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: boolreturn self.isBalancedCore(root)6.12 二叉树的所有路径 题目leetcode 257 思路前序遍历保证root指向孩子节点 确定终止条件递归过程中到叶子节点就可以停止做收集了没必要到空节点递归过程中要做回溯path不能一直加入节点还要删节点然后才能加入新的节点回溯和递归是一一对应的有一个递归就要有一个回溯

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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不能一直加入节点还要删节点然后才能加入新的节点回溯和递归是一一对应的有一个递归就要有一个回溯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 result6.13 左叶子之和 题目leetcode 404 思路 判断当前节点是不是左叶子要通过节点的父节点判断其左孩子是不是左叶子即如果该节点的左节点不为空该节点的左节点的左节点为空该节点的左节点的右节点为空则找到了一个左叶子遇到左叶子节点时记录数值递归分别求左右子树的左叶子和相加就是整个树的左叶子之和

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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: intif not root:return 0return self.get_left_sum(root)6.14 找树左下角的值 题目leetcode 513 思路 1、递归回溯 找到叶子节点那一层也就是深度最大的叶子节点然后保证优先左边搜索

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

self.val val

self.left left

self.right right

class Solution(object):m_depth float(-inf)result 0def travalsal(self, root, depth):# 找到叶子节点那一层也就是深度最大的叶子节点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: intif not root:return 0self.travalsal(root, 0)return self.result 2、层序遍历

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

self.val val

self.left left

self.right right

class Solution(object):def findBottomLeftValue(self, root)::type root: Optional[TreeNode]:rtype: intif 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 result6.15 路径总和 题目leetcode 112 思路递归 搜索整个二叉树其中一条路径递归就需要返回值来保证在遇到符合条件的路径时及时返回使用递减如果最后sum为0且同时到了叶子节点则找到了目标路径否则就是没找到

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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: boolif not root:return False# 搜索进去节点之前应该让数已经减过了return self.traversal(root, targetSum - root.val) 6.16 路径总和2 题目leetcode 113 思路递归 当需要搜索整棵二叉树不止一条路径且不需要处理返回值的时候递归函数就不需要返回值。思路类似6.15这里需要注意的是在递归过程中如果是self.result.append(self.path)那么 self.result 中的每个元素都将是对 self.path 的引用。由于 self.path 是一个可变的列表在递归过程中每次修改 self.path 都会影响到已经添加到 self.result 中的路径。通过使用 self.path[:]或者list(self.path)我们创建了 self.path 的一个副本这样每次添加到 self.result 中的路径都是独立的不会受到后续修改 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 result6.17 从中序和后序遍历序列构造二叉树 题目leetcode 106 思路从后序数组的最后一个元素为切割点切割中序数组再由切割后的中序数组切割后序数组

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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[idx1:]post_left_list postorder[0:len(in_left_list)]post_right_list postorder[len(post_left_list):len(in_right_list)1]mid TreeNode(valmid_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 从前序和中序遍历序列构造二叉树 题目leetcode 105 思路先从前序遍历第一个节点作为中序遍历序列的分割点然后取出中序遍历的左右区间对应再取出前序遍历的左右区间递归即可

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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_idx1:]pre_left preorder[1:len(in_left)1]pre_right preorder[len(in_left)1:]mid_node TreeNode(valmid_node_val)mid_node.left self.buildTree(pre_left, in_left)mid_node.right self.buildTree(pre_right, in_right)return mid_node6.19 最大二叉树 题目leetcode 654 思路找最大值去分割左右区间递归即可

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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(valmax_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_idx1:]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 思路合并两棵树定一个merge函数同时操作就可以了

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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(valroot2.val, leftNone, rightNone)if not root2:return TreeNode(valroot1.val, leftNone, rightNone)node TreeNode(valroot1.valroot2.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是有序的递归时如果值与根节点相等直接返回如果比根节点大那么在右子树搜索否则在左子树搜索

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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 验证二叉搜索树 题目leetcode 98 思路 方案1 BST中序遍历是一个有序数组看这个数组是否有序

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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: boolself.is_valid_bst(root)for idx in range(1, len(self.visited)):if self.visited[idx] self.visited[idx-1]:return Falsereturn True 方案2 遍历过程中判断这里为什么不能root.left.val root.val root.right.val是因为没有判断整棵子树所有节点双指针用pre记录当前遍历的前一个节点跟有序数组一样判断后一个是不是比前一个大

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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: boolreturn self.is_valid_bst(root)6.23 二叉搜索树的最小绝对差 题目leetcode 530 思路BST求最值类的题目其实就是在有序数组上求最值。使用双指针来在遍历过程中比较前一个节点和后一个节点即可最值只可能在这里面产生

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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: intself.traversal(root)return self.min_diff 6.24 二叉搜索树中的众数 题目leetcode 501 思路 方案1: 遍历然后用map统计

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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来统计单个元素出现的频率用max_count来维护树中出现最多的频率另外在这里要注意在递归调用时如果要更新和使用pre需要将pre作为实例变量才可以正确更新self.pre的值所以最好都使用这种方法

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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:# 不相等时cnt继续统计单一元素出现的频率self.cnt 1self.pre rootif self.cnt self.max_cnt:self.result.append(root.val)# 当 cntmax_cnt 放进来结果集时有可能max_cnt还不是最大的频率所以要动态更新max_cnt并把之前不符合要求的结果清掉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 思路自底向上遍历但平时都是从上开始遍历的这时就要用到回溯来把公共祖先传递上去并且要使用后序遍历因为是左右中。在传递向上的过程中 如果root是p/q中的一个那么直接返回不走下面的递归否则开始后序遍历如果左子树返回不为空则可能出现了p/q右子树同理当都不为空则当前这个点就是最近公共祖先

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: TreeNodereturn self.traversal(root, p, q)

6.26 二叉搜索树的最近公共祖先 题目leetcode 235 思路利用BST的有序特性 如果p和q都比当前遍历的节点小那么应该向左遍历否则应该向右遍历如果当前遍历这个节点的值在p和q之间这个节点就是p和q的公共节点因为在此分叉了所以这个节点就是最近的公共祖先

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: TreeNodereturn self.traversal(root, p, q)

6.27 二叉搜索树中的插入操作 题目leetcode 701 思路利用二叉树的有序特性值小就往左边插值大就往右边插最后返回root

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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(valval)if root.val val:root.left self.insertIntoBST(root.left, val)if root.val val:root.right self.insertIntoBST(root.right, val)return root6.28 删除二叉搜索树中的节点 题目leetcode 450 思路尝试找到这个节点然后删除它 1、如果没找到返回空下面都是找到了的情况 2、如果删的是叶子节点左为空右也为空直接删除返回None当前层的左子树等于下一层递归的返回值 3、如果删的节点左不空右为空把左子树挂在当前节点的父节点的左边 4、如果删的节点左为空右不空把右子树挂在当前节点的父节点的右边 5、如果删的节点左不空右不空以右子树为例要找到这个子树上最小的那个节点右子树最左侧用迭代一直往左走然后把左子树挂上去最后回到左为空右不为空的情况

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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 思路 这里通过root.val low or root.val high然后返回空来删除节点是错误的因为不能保证其中一个条件生效时它的子树也都是满足条件的这样子树会都被删除

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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:# 递归右子树并返回右子树符合条件的头节点return self.trim(root.right, low, high)if root.val high:return self.trim(root.left, low, high)# 把下一层处理完左/右子树的结果赋给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 构造平衡二叉搜索树 题目leetcode 108 思路一定要选取数组里面中间的节点这样左右区间的节点数量才是相同的这样的二叉树才是平衡的。分割成左右区间后继续去构造二叉树即可

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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(valnums[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 把二叉搜索树转换为累加树 题目leetcode 538 思路把左中右变成右中左遍历。和数组一样使用双指针累加

Definition for a binary tree node.

class TreeNode(object):

def init(self, val0, leftNone, rightNone):

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