代码随想录 leetcode-数据结构刷题笔记
文章目录
- 一、数组
- 二、链表
- 三、哈希表
- 四、字符串
- 五、栈和队列
- 六、二叉树
- 6.1 二叉树种类
- 6.2 二叉树的存储
- 6.3 二叉树的遍历
- 6.4 二叉树层序遍历相关
- 6.5 翻转二叉树
- 6.6 对称二叉树
- 6.7 相同的树
- 6.8 另一个树的子树
- 6.9 二叉树的最小深度
- 6.10 完全二叉树的节点个数
- 6.11 平衡二叉树
- 6.12 二叉树的所有路径
- 6.13 左叶子之和
- 6.14 找树左下角的值
- 6.15 路径总和
- 6.16 路径总和2
- 6.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 = 0
right = len(nums) - 1
while (left <= right):
mid = left + (right - left) / 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1
1.1.2 搜索插入位置
题目：leetcode 35
思路：二分
class Solution(object):
def searchInsert(self, nums, target):
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left) / 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
return right + 1
1.1.3 排序数组中查找元素第一和最后一个位置
题目：leetcode 34
思路：
- 1、找第一个位置：先二分模板，然后思考相等以后什么时候要往左找？——在mid-1上的元素如果都大于等于target时（需要确保mid-1合法），说明第一个位置还在左边。否则mid位置就是第一个。找不到就是-1。
- 2、找最后一个位置：先二分模板，然后思考相等以后什么时候要往右找？——在mid+1上的元素小于等于target时（需要确保mid+1合法），说明最后一个位置还在右边。否则mid位置就是最后一个。找不到就是-1
class Solution(object):
def search_first(self, nums, target):
left = 0
right = len(nums) - 1
while (left <= right):
mid = left + (right - left) / 2
if nums[mid] == target:
if mid > 1 and nums[mid-1] >= target:
right = mid - 1
else:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
def search_right(self, nums, target):
left = 0
right = len(nums) - 1
while (left <= right):
mid = left + (right - left) / 2
if nums[mid] == target:
if mid < len(nums) - 1 and nums[mid+1] <= target:
left = mid + 1
else:
return mid
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1
def 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 = 0
right = x
ans = -1
while left <= right:
mid = left + (right - left) / 2
if mid * mid < x:
left = mid + 1
ans = mid
elif mid * mid > x:
right = mid - 1
else:
left = mid + 1
ans = mid
return ans
1.1.5 有效的完全平方数
题目：leetcode 367
思路：同1.1.4
class Solution:
def isPerfectSquare(self, num):
left, right = 0, num
while left <= right:
mid = left + (right - left) / 2
square = mid * mid
if square < num:
left = mid + 1
elif square > num:
right = mid - 1
else:
return True
return False
1.2 快慢指针
1.2.1 移除元素
题目：leetcode 27
思路：使用快慢指针，快指针：获取数组元素；慢指针：获取新数组中需要更新的位置
class Solution(object):
def removeElement(self, nums, val):
fast = 0
slow = 0
for fast in range(0, len(nums)):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
return slow
1.2.2 删除有序数组中的重复项
题目：leetcode 26
思路：快慢指针
class Solution(object):
def removeDuplicates(self, nums):
slow = 1
num = nums[0]
for fast in range(1, len(nums)):
if nums[fast] != num:
nums[slow] = nums[fast]
num = nums[fast]
slow += 1
return slow
1.2.3 移动0
题目：leetcode 283
思路：快慢指针，快指针找到不为0的和慢指针上的元素交换
class Solution(object):
def moveZeroes(self, nums):
slow = 0
fast = 0
for fast in range(0, len(nums)):
if nums[fast] != 0:
tmp = nums[slow]
nums[slow] = nums[fast]
nums[fast] = tmp
slow += 1
1.2.4 比较含退格的字符串
题目：leetcode 844
思路：分别记录两个字符串中退格的个数。i、j指针从后往前遍历，目的是把退格跳过，然后比较i和j上的元素
class Solution(object):
def backspaceCompare(self, s, t):
i = len(s) - 1
j = len(t) - 1
skip_s = 0
skip_t = 0
while (i >= 0 and j >= 0):
while i >= 0:
if s[i] == '#':
skip_s += 1
else:
if skip_s > 0:
skip_s -= 1
else:
break
i -= 1
while j >= 0:
if t[j] == '#':
skip_t += 1
else:
if skip_t > 0:
skip_t -= 1
else:
break
j -= 1
if s[i] != t[j]:
return False
i -= 1
j -= 1
return True
1.2.5 有序数组的平方
题目：leetcode 977
思路：从后往前遍历，保证最后的数是最大的，中间做元素交换和覆盖即可
class Solution(object):
def sortedSquares(self, nums):
right = len(nums) - 1
while 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_value
else:
nums[right] = r_value
right -= 1
return nums
1.3 滑动窗口
1.3.1 长度最小的子数组
题目：leetcode 209
思路：滑动窗口，j表示终止位置，i表示起始位置。终止位置不断移动求和，当发现其和大于等于目标值时，不断移动起始位置，另外减少和，在这个过程中计算出窗口的最小长度即可。特殊情况是所有加起来都没有大于目标值，那么对这种情况返回0即可
class Solution(object):
def minSubArrayLen(self, target, nums):
i = 0
s = 0
result = len(nums)
flag = False
for j in range(0, len(nums)):
s = s + nums[j]
while (s >= target):
flag = True
sub_len = j - i + 1
result = min(result, sub_len)
s = s - nums[i]
i = i + 1
return result if flag else 0
1.3.2 水果成篮
题目：leetcode 904
思路：这里fruits中的每个元素代表第i棵树上的水果种类，而不是种类数。所以只要保证两个篮子里装了两个种类的水果即可。右指针从0开始，把水果捡进篮子，篮子内只要超过2个，就开始去丢最左边的水果，丢了之后移动左指针，然后计算最大距离即可
class Solution(object):
def totalFruit(self, fruits):
bucket = defaultdict(int)
res = left = right = 0
for right in range(len(fruits)):
bucket[fruits[right]] += 1
while (len(bucket) > 2):
bucket[fruits[left]] -= 1
if bucket[fruits[left]] == 0:
del bucket[fruits[left]]
left += 1
res = max(res, right - left + 1)
return res
1.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: str
"""
if len(t) > len(s):
return ""
# hs统计当前窗口中各个字符的数量
hs = collections.defaultdict(int)
ht = collections.defaultdict(int)
# 统计t中各字符数量到ht中
for char in t:
ht[char] += 1
j = i = 0
cnt = 0
res_sub_str = ""
min_length = len(s) + 1
# 移动右边指针
for j in range(len(s)):
# 往hs添加当前字符
hs[s[j]] += 1
# 如果添加的字符没有超过ht中对应字符的数量，那么有效字符+1
if hs[s[j]] <= ht[s[j]]:
cnt += 1
# 看是否移动左边指针，当hs中对应元素的数量大于ht中对应元素的数量，说明是冗余字符，需要删去且左指针往前走
while i <= j and hs[s[i]] > ht[s[i]]:
hs[s[i]] -= 1
i += 1
# 当有效字符数和t的长度相同，那么更新最小窗口大小，并取窗口内的子字符串
if cnt == len(t):
if (j - i + 1) < min_length:
min_length = j - i + 1
res_sub_str = s[i:j+1]
return res_sub_str
1.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 = 0
i = j = 0
start_row = start_col = 0
offset = 1
num = 1
while loop < n / 2:
for j in range(start_col, n - offset):
m[start_row][j] = num
num += 1
j += 1
for i in range(start_row, n - offset):
m[i][j] = num
num += 1
i += 1
for j in range(j, start_col, -1):
m[i][j] = num
num += 1
j -= 1
for i in range(i, start_row, -1):
m[i][j] = num
num += 1
i -= 1
start_row += 1
start_col += 1
offset += 1
loop += 1
if n % 2 == 1:
m[start_row][start_col] = num
return m
二、链表
链表是通过指针串联在一起的线性结构，但在内存中不是连续分布的，分配机制取决于os的内存管理。
每个节点由数据域和指针域组成，类型有
- 单链表
- 双链表：每个节点有两个指针域，分别指向前一个节点和后一个节点
- 循环链表：链表首尾相连，通常解决约瑟夫环的问题
对比数组（插入/删除O(n)，查询O(1)），链表的时间复杂度为（插入/删除O(1)，查询O(n)）
链表长度不固定，适合频繁增删，较少查询的场景
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
2.1 移除链表元素
题目：leetcode 203
思路：有两种方式
- 直接在原链表进行删除操作：其他节点都是通过前一个节点来删除当前节点的，头节点没有前一个节点，操作比较难统一
- 设置一个虚拟头节点再进行删除操作：统一删除操作，从链表最前端dummy节点开始判断下一个元素是否和val相同，相同则进行删除操作并移动指针，否则移动当前指针到下一个元素
常规删除：
# 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 None
dummy = ListNode(next=head)
cur = dummy
while cur.next is not None:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return 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 None
head.next = self.removeElements(head.next, val)
if head.val == val:
return head.next
else:
return head
2.2 设计链表
题目：leetcode 707
思路：如代码所示，添加和删除都是先找到位置，断开原链，加上新链
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class MyLinkedList(object):
def __init__(self):
self.dummy = ListNode()
self.size = 0
def get(self, index):
"""
校验index合法性，从虚拟头节点的下一个节点开始遍历链表取值即可
"""
if index < 0 or index >= self.size:
return -1
cur = self.dummy.next
for idx in range(0, index):
cur = cur.next
return cur.val
def addAtHead(self, val):
"""
让dummy节点的下一个节点是头节点即可
"""
self.dummy.next = ListNode(val=val)
self.size += 1
def addAtTail(self, val):
"""
遍历到最后一个节点，在最后一个节点后面新增一个节点即可
"""
cur = self.dummy
while cur.next is not None:
cur = cur.next
cur.next = ListNode(val=val)
self.size += 1
def addAtIndex(self, index, val):
"""
新增节点时，遍历到要添加的位置，让当前节点的next指向新节点，新节点的next是当前节点的next
"""
if index < 0 or index >= self.size:
return
cur = self.dummy
for idx in range(0, index):
cur = cur.next
cur.next = ListNode(val=val, next=cur.next)
self.size += 1
def deleteAtIndex(self, index):
"""
删除节点时，遍历到要删除的位置，让当前节点的next指向下下个节点即可
"""
if index < 0 or index >= self.size:
return
cur = self.dummy
for idx in range(0, index):
cur = cur.next
cur.next = cur.next.next
self.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, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
cur = head
pre = None
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
方案2:递归法，和双指针法一样的思路，递归初始，pre指针指向空，cur指向头节点，每次递归保存cur的下一个节点到tmp，改变cur的next指向到pre，然后移动pre指针，移动cur指针，直到cur为空时结束递归返回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 pre
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return self.reverse(pre, cur)
def reverseList(self, head):
return self.reverse(None, head)
2.4 两两交换链表中的节点
题目：leetcode 24
方案1:
- 思路：设定头节点，当前节点为头节点，暂存1、2、3号元素，把cur指向2，2指向1，1指向3，最后cur往前走两步，直到cur的next和next、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 swapPairs(self, head):
dummy = ListNode(next=head)
cur = dummy
# 必须有cur的下一个和下下个才能交换，否则说明已经交换结束了
while cur.next and cur.next.next:
tmp1 = cur.next
tmp2 = cur.next.next
tmp3 = cur.next.next.next
cur.next = tmp2
tmp2.next = tmp1
tmp1.next = tmp3
cur = cur.next.next
return dummy.next
方案2:
- 思路：递归，不使用头节点，pre指向头节点，cur指向head.next，next是head.next.next，每次交换pre和cur，然后把nxt当作头节点继续交换，最后返回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 head
pre = head
cur = head.next
nxt = head.next.next
cur.next = pre
pre.next = self.swapPairs(nxt)
return cur
2.5 删除链表的倒数第N个节点
题目：leetcode 19
思路：使用快慢指针，快慢指针同时指向dummy虚拟头节点，快指针先走，走到头了慢指针就可以删了
# 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 = dummy
while n >= 0 and fast:
fast = fast.next
n -= 1
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return 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 = None
class Solution(object):
def getListNodeLen(self, head):
l = 0
cur = head
while cur:
cur = cur.next
l += 1
return l
def run(self, head, n):
cur = head
for i in range(0, n):
cur = cur.next
return cur
def getIntersectionNode(self, headA, headB):
len_a = self.getListNodeLen(headA)
len_b = self.getListNodeLen(headB)
fast = slow = None
if len_a > len_b:
fast = self.run(headA, len_a - len_b)
slow = headB
else:
fast = self.run(headB, len_b - len_a)
slow = headA
while fast and slow:
if fast == slow:
return fast
fast = fast.next
slow = slow.next
return None
2.7 环形链表
题目：leetcode 142
方案1:
- 直接用set，看是否已存在，存在即可返回
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
visited = set()
cur = head
while cur:
if cur in visited:
return cur
visited.add(cur)
cur = cur.next
return None
方案2:
- 快慢指针：快指针走两步、慢指针走一步，相遇则说明链表有环。相遇以后，慢指针回头，快慢指针一步一步走，直到相遇则为环入口
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
fast = slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return 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: bool
"""
record = [0] * 26
for i in range(0, len(s)):
record[ord(s[i]) - ord('a')] += 1
for i in range(0, len(t)):
record[ord(t[i]) - ord('a')] -= 1
for i in range(0, len(record)):
if record[i] != 0:
return False
return True
或者使用defaultdict也可以
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
from collections import defaultdict
record = defaultdict(int)
for i in range(0, len(s)):
record[s[i]] += 1
for i in range(0, len(t)):
record[t[i]] -= 1
for k, v in record.items():
if v != 0:
return False
return True
3.3 字母异位词分组
题目：leetcode 49
思路：遍历每个元素，对每个元素排序放到列表中即可
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
from collections import defaultdict
ret = []
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 == s2
def 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
思路：记录一个单词出现的次数，再遍历另一个单词，减去出现的次数，如果出现负数，说明不能组成
class Solution(object):
def canConstruct(self, ransomNote, magazine):
from collections import defaultdict
m = defaultdict(int)
for i in range(0, len(magazine)):
m[magazine[i]] += 1
for i in range(0, len(ransomNote)):
m[ransomNote[i]] -= 1
for k, v in m.items():
if v < 0:
return False
return True
3.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] = 1
for 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)) + 1
m1 = [0] * l
m2 = [0] * l
for item in nums1:
m1[item] += 1
for item in nums2:
m2[item] += 1
ret = []
for i in range(0, l):
if m1[i] * m2[i] > 0:
ret.append(i)
return ret
3.7 快乐数
题目：leetcode 202
思路：求和时，通过模10获取整数每一位上的数字，然后除以10更新数字；每一轮看求和数是否出现在哈希表中即可判断是否进入死循环
class Solution(object):
def get_sum(self, n):
s = 0
while n > 0:
num = n % 10
s += num * num
n = n / 10
return s
def isHappy(self, n):
visited = set()
while True:
s = self.get_sum(n)
print n, s
if s == 1:
return True
if s in visited:
return False
else:
visited.add(s)
n = s
return 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]] = i
return [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 四数相加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: 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] += 1
else:
m[s] = 1
cnt = 0
for 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 = 0
j = len(s) - 1
while i < j:
tmp = s[i]
s[i] = s[j]
s[j] = tmp
i += 1
j -= 1
4.2 反转字符串II
题目：leetcode 541
思路：使用range，步长为2k，然后取每个步长的k个字符来进行反转即可
class Solution(object):
def reverse_sub(self, sub):
i = 0
j = len(sub) - 1
while i < j:
tmp = sub[i]
sub[i] = sub[j]
sub[j] = tmp
i += 1
j -= 1
return sub
def 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 反转字符串里的单词
题目：leetcode 151
思路：使用split函数分割然后交换元素即可
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
l = s.split(" ")
res = list()
j = len(l) - 1
while j >= 0:
if l[j] != "":
res.append(l[j])
j -= 1
return " ".join(res)
在Python 2中，字符串的 split() 方法用于将字符串拆分成一个列表。如果你不提供任何参数，split() 方法会将字符串按空白字符（空格、制表符、换行符等）进行拆分，并自动去除字符串两端的空白字符和多余的空白字符。
class Solution:
def reverseWords(self, s: str) -> str:
# 将字符串拆分为单词，即转换成列表类型
words = s.split()
# 反转单词
left, right = 0, len(words) - 1
while left < right:
words[left], words[right] = words[right], words[left]
left += 1
right -= 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: None
"""
self.queue1.append(x)
while self.queue2:
self.queue1.append(self.queue2.popleft())
self.queue1, self.queue2 = self.queue2, self.queue1
def 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 有效的括号
题目：leetcode 20
思路：遍历字符串，每遇到一个左括号，就填一个右括号进入栈中，遍历到右括号时，看是否相等，相等就pop右括号出来；最后如果右括号和最后一个元素不相等或者栈为空，那么说明括号不是有效的
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 False
else:
stack.pop()
return True
5.4 删除字符串中所有的相邻重复项
思路：遍历字符串，栈中存放遍历过的元素，如果栈不为空且最后一个元素和当前元素相等，那么pop；否则遍历放元素进去即可
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 逆波兰表达式求值
题目：leetcode 150
思路：碰到数字就放到栈里，否则碰到运算符时，从栈中取两个元素做对应运算，把结果放到栈里即可
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 = 0
if item == "+":
t = t1 + t2
elif item == "-":
t = t2 - t1
elif item == "*":
t = t1 * t2
elif 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 deque
class 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 heapq
data = [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) + 1
min_heap = []
for key, freq in m.items():
heapq.heappush(min_heap, (freq, key))
# 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
if 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*i+1，右孩子是2*i+2
6.3 二叉树的遍历
两种遍历方式：
-
深度优先遍历：先往深走，遇到叶子节点再往回走。包括前序（中左右）、中序（左中右）、后序（左右中）遍历（
前中后序指的就是中间节点的位置），一般使借助栈使用递归来实现
-
广度优先遍历：一层一层遍历。包括层序遍历，一般使用队列来实现
1、前序遍历
题目：leetcode 144
迭代法：使用栈来模拟递归，前序遍历是中左右，先将根节点入栈，然后右、左；保证出栈时处理时放到数组的元素顺序是中左右
# 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:
return
res.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, 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 = 0
j = len(ret) - 1
while i < j:
ret[i], ret[j] = ret[j], ret[i]
i += 1
j -= 1
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:
return
self.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, 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() # 不能提前把根节点加到栈中，要先找到左子树最底部
cur = root
while cur or len(stack) > 0:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return 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:
return
dfs(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 = []
# 每层元素先进先出
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
# 每到新的一层，加一个空数组准备收集这一层的元素
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 二叉树层序遍历相关
6.4.1 二叉树层序遍历II
题目：leetcode 107
思路：使用队列做二叉树层序遍历，然后逆序输出即可
# 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
思路：其实就是层序遍历，找到每一层的最后一个节点即可
# 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 deque
ret = []
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是个数组
"""
# Definition for a Node.
class Node(object):
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution(object):
def levelOrder(self, root):
"""
:type root: Node
:rtype: List[List[int]]
"""
from collections import deque
ret = []
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, 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 deque
ret = []
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 填充每个节点的下一个右侧节点指针
题目：leetcode 116
思路：层序遍历，遍历每一层所有节点之前，维护一个prev记录这一层所有节点的前一个节点，如果有这个prev，那么就把prev的next指向当前节点，然后更新prev
"""
# Definition for a Node.
class Node(object):
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution(object):
def connect(self, root):
"""
:type root: Node
:rtype: Node
"""
if not root:
return root
from collections import deque
level_queue = deque()
level_queue.append(root)
while level_queue:
prev = None
for _ in range(0, len(level_queue)):
cur = level_queue.popleft()
if prev:
prev.next = cur
prev = cur
if 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 0
from collections import deque
deep = 0
level_queue = deque()
level_queue.append(root)
while level_queue:
deep += 1
for _ 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, 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 0
from collections import deque
deep = 0
level_queue = deque()
level_queue.append(root)
while level_queue:
deep += 1
for _ 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 deep
return deep
6.5 翻转二叉树
题目：leetcode 226
思路：
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 invertTree(self, root):
"""
:type root: Optional[TreeNode]
:rtype: Optional[TreeNode]
"""
if not root:
return root
tmp = root.left
root.left = root.right
root.right = tmp
self.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 root
stack = [root]
while stack:
cur = stack.pop()
cur.left, cur.right = cur.right, cur.left
if 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 root
from collections import deque
my_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.left
if node.left:
my_queue.append(node.left)
if node.right:
my_queue.append(node.right)
return root
6.6 对称二叉树
题目：leetcode 101
思路：比较左子树和右子树是不是互相翻转的，即是要比较两棵树。只能是后序遍历，一棵树遍历顺序是左右中，另一棵树遍历顺序是右左中
递归法：
# 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):
"""
要比较的是根节点的两个子树是否是相互翻转，所以要比较的是两个树，参数是左子树节点和右子树根节点，返回值是bool
"""
def compare(self, left, right):
if left is None and right:
return False
elif right is None and left:
return False
elif left is None and right is None:
return True
elif left.val != right.val:
return False
else:
outside = self.compare(left.left, right.right)
inside = self.compare(left.right, right.left)
return outside and inside
def isSymmetric(self, root):
"""
:type root: Optional[TreeNode]
:rtype: bool
"""
if not root:
return True
return self.compare(root.left, root.right)
迭代法：类似层序遍历，每一层遍历按左节点左孩子，右节点右孩子，左节点右孩子，右节点左孩子入队列
# 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 True
from collections import deque
my_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:
continue
if left_node.left is None and right_node.right:
return False
elif left_node.right is None and right_node.left:
return False
elif left_node is None and right_node is None:
return True
else:
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, 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 False
elif right is None and left:
return False
elif left is None and right is None:
return True
elif left.val != right.val:
return False
else:
left_compare = self.compare(left.left, right.left)
right_compare = self.compare(left.right, right.right)
return left_compare and right_compare
def isSameTree(self, p, q):
"""
:type p: Optional[TreeNode]
:type q: Optional[TreeNode]
:rtype: bool
"""
return self.compare(p, q)
6.8 另一个树的子树
题目：leetcode 572
思路：层序遍历每个大树的节点，判断每个节点是否和另一个树是子树关系即可
# 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 False
elif right and left is None:
return False
elif left is None and right is None:
return True
else:
left_same = self.compare(left.left, right.left)
right_same = self.compare(left.right, right.right)
return left_same and right_same
def isSubtree(self, root, subRoot):
"""
:type root: Optional[TreeNode]
:type subRoot: Optional[TreeNode]
:rtype: bool
"""
if not root:
return False
from collections import deque
my_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 True
if 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, 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 0
h_left = self.get_depth(root.left)
h_right = self.get_depth(root.right)
if root.left and root.right is None:
return 1 + h_left
if root.right and root.left is None:
return 1 + h_right
return 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)
迭代法：层序遍历记录高度，当碰到左右子树都为空的节点，返回此时的高度即可
# 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 0
from collections import deque
my_queue = deque()
my_queue.append(root)
depth = 0
while my_queue:
depth += 1
for _ 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 depth
return depth
6.10 完全二叉树的节点个数
题目：leetcode 222
思路：完全二叉树是指除了最底下一层没填满，其他都填满了的二叉树
递归，分别求左右子树的节点个数，最后加起来即可
# 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 0
cnt_left = self.cnt(root.left)
cnt_right = self.cnt(root.right)
return 1 + cnt_left + cnt_right
def 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 0
from collections import deque
my_queue = deque()
my_queue.append(root)
cnt = 0
while my_queue:
for _ in range(0, len(my_queue)):
node = my_queue.popleft()
cnt += 1
if node.left:
my_queue.append(node.left)
if node.right:
my_queue.append(node.right)
return cnt
6.11 平衡二叉树
题目：leetcode 110
思路：平衡二叉树的定义是一个二叉树每个节点的左右两个字树的高度差不超过1。于是我们可以去求每个节点的高度，递归过程中判断左右子树的高度差是否超过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 0
left_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 True
if abs(self.get_depth(root.left) - self.get_depth(root.right)) > 1:
return False
return 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指向孩子节点
- 确定终止条件：递归过程中，到叶子节点就可以停止做收集了，没必要到空节点
- 递归过程中要做回溯，path不能一直加入节点，还要删节点，然后才能加入新的节点，回溯和递归是一一对应的，有一个递归，就要有一个回溯
# 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)))
return
if 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 result
6.13 左叶子之和
题目：leetcode 404
思路：
- 判断当前节点是不是左叶子要通过节点的父节点判断其左孩子是不是左叶子，即如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子
- 遇到左叶子节点时，记录数值，递归分别求左右子树的左叶子和，相加就是整个树的左叶子之和
# 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 0
if not root.left and not root.right:
return 0
left_val = self.get_left_sum(root.left)
if root.left and not root.left.left and not root.left.right:
left_val = root.left.val
right_val = self.get_left_sum(root.right)
return left_val + right_val
def sumOfLeftLeaves(self, root):
"""
:type root: Optional[TreeNode]
:rtype: int
"""
if not root:
return 0
return self.get_left_sum(root)
6.14 找树左下角的值
题目：leetcode 513
思路：
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):
m_depth = float('-inf')
result = 0
def travalsal(self, root, depth):
# 找到叶子节点那一层（也就是深度最大的叶子节点）
if not root.left and not root.right:
if self.m_depth < depth:
self.m_depth = depth
self.result = root.val
return
if root.left:
depth += 1
self.travalsal(root.left, depth)
depth -= 1 # 回溯
if root.right:
depth += 1
self.travalsal(root.right, depth)
depth -= 1
def findBottomLeftValue(self, root):
"""
:type root: Optional[TreeNode]
:rtype: int
"""
if not root:
return 0
self.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 0
from collections import deque
my_queue = deque()
my_queue.append(root)
result = root.val
while my_queue:
for idx in range(0, len(my_queue)):
node = my_queue.popleft()
if idx == 0:
result = node.val
if node.left:
my_queue.append(node.left)
if node.right:
my_queue.append(node.right)
return result
6.15 路径总和
题目：leetcode 112
思路：递归
- 搜索整个二叉树其中一条路径，递归就需要返回值来保证在遇到符合条件的路径时及时返回
- 使用递减，如果最后sum为0且同时到了叶子节点，则找到了目标路径；否则就是没找到
# 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 True
return False
if root.left:
target_sum -= root.left.val
if self.traversal(root.left, target_sum):
return True
target_sum += root.left.val
if root.right:
target_sum -= root.right.val
if self.traversal(root.right, target_sum):
return True
target_sum += root.right.val
return False
def hasPathSum(self, root, targetSum):
"""
:type root: Optional[TreeNode]
:type targetSum: int
:rtype: bool
"""
if 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[:])
return
if root.left:
target -= root.left.val
path.append(root.left.val)
self.traversal(root.left, path, target, result)
target += root.left.val
path.pop()
if root.right:
target -= root.right.val
path.append(root.right.val)
self.traversal(root.right, path, target, result)
target += root.right.val
path.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 从中序和后序遍历序列构造二叉树
题目：leetcode 106
思路：从后序数组的最后一个元素为切割点切割中序数组，再由切割后的中序数组切割后序数组
# 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 None
mid_node = postorder[-1]
mid_node_idx = 0
for idx in range(0, len(inorder)):
if inorder[idx] == mid_node:
mid_node_idx = idx
break
in_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 mid
def 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, 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 None
mid_node_val = preorder[0]
mid_node_idx = 0
for idx in range(0, len(inorder)):
if inorder[idx] == mid_node_val:
mid_node_idx = idx
break
in_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
思路：找最大值去分割左右区间，递归即可
# 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 None
max_val = max(nums)
mid = TreeNode(val=max_val)
mid_idx = 0
for idx in range(0, len(nums)):
if nums[idx] == max_val:
mid_idx = idx
break
l_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 mid
def 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, 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 None
if 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 node
def 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, 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 None
if root.val == val:
return root
if val < root.val:
return self.search(root.left, val)
if val > root.val:
return self.search(root.right, val)
return None
def 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, 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 True
self.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 False
return True
方案2
- 遍历过程中判断，这里为什么不能root.left.val < root.val < root.right.val，是因为没有判断整棵子树所有节点
- 双指针，用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.pre = None
def is_valid_bst(self, root):
if not root:
return True
l = self.is_valid_bst(root.left)
if self.pre and self.pre.val >= root.val:
return False
self.pre = root
r = self.is_valid_bst(root.right)
return l and r
def isValidBST(self, root):
"""
:type root: Optional[TreeNode]
:rtype: bool
"""
return self.is_valid_bst(root)
6.23 二叉搜索树的最小绝对差
题目：leetcode 530
思路：BST求最值类的题目，其实就是在有序数组上求最值。使用双指针来在遍历过程中比较前一个节点和后一个节点即可，最值只可能在这里面产生
# 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 = None
def traversal(self, root):
if not root:
return
self.traversal(root.left)
if self.pre:
self.min_diff = min(self.min_diff, abs(root.val - self.pre.val))
self.pre = root
self.traversal(root.right)
def getMinimumDifference(self, root):
"""
:type root: Optional[TreeNode]
:rtype: int
"""
self.traversal(root)
return self.min_diff
6.24 二叉搜索树中的众数
题目：leetcode 501
思路：
方案1:
- 遍历，然后用map统计
# 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 defaultdict
self.m = defaultdict(int)
def traversal(self, root):
if not root:
return
self.traversal(root.left)
self.m[root.val] += 1
self.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, 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 = 0
self.cnt = 0
self.pre = None
def traversal(self, root):
if not root:
return
self.traversal(root.left)
if not self.pre:
self.cnt = 1
elif self.pre.val == root.val:
self.cnt += 1
else:
# 不相等时，cnt继续统计单一元素出现的频率
self.cnt = 1
self.pre = root
if self.cnt == self.max_cnt:
self.result.append(root.val)
# 当 cnt==max_cnt 放进来结果集时，有可能max_cnt还不是最大的频率，所以要动态更新max_cnt，并把之前不符合要求的结果清掉
if self.cnt > self.max_cnt:
self.max_cnt = self.cnt
self.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 = None
class Solution(object):
def traversal(self, root, p, q):
if not root:
return None
if root in [p, q]:
return root
l = self.traversal(root.left, p, q)
r = self.traversal(root.right, p, q)
if l and not r:
return l
elif r and not l:
return r
elif r and l:
return root
else:
return None
def 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都比当前遍历的节点小，那么应该向左遍历，否则应该向右遍历
- 如果当前遍历这个节点的值在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 = None
class Solution(object):
def traversal(self, root, p, q):
if not root:
return None
if root.val > p.val and root.val > q.val:
left = self.traversal(root.left, p, q)
if left:
return left
elif root.val < p.val and root.val < q.val:
right = self.traversal(root.right, p, q)
if right:
return right
else:
return root
def 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 删除二叉搜索树中的节点
题目：leetcode 450
思路：尝试找到这个节点，然后删除它
1、如果没找到，返回空；下面都是找到了的情况
2、如果删的是叶子节点（左为空，右也为空），直接删除，返回None，当前层的左子树等于下一层递归的返回值
3、如果删的节点左不空，右为空，把左子树挂在当前节点的父节点的左边
4、如果删的节点左为空，右不空，把右子树挂在当前节点的父节点的右边
5、如果删的节点左不空，右不空；以右子树为例，要找到这个子树上最小的那个节点（右子树最左侧，用迭代一直往左走），然后把左子树挂上去，最后回到左为空，右不为空的情况
# 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 None
if root.val == key:
if not root.left and not root.right:
return None
elif root.left and not root.right:
return root.left
elif root.right and not root.left:
return root.right
elif root.left and root.right:
cur = root.right
while cur.left:
cur = cur.left
cur.left = root.left
return root.right
if root.val > key:
root.left = self.delete(root.left, key)
if root.val < key:
root.right = self.delete(root.right, key)
return root
def 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, 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 None
if root.val < low:
# 递归右子树并返回右子树符合条件的头节点
return self.trim(root.right, low, high)
if root.val > high:
return self.trim(root.left, low, high)
# 把下一层处理完左/右子树的结果赋给root.left/root.right
root.left = self.trim(root.left, low, high)
root.right = self.trim(root.right, low, high)
return root
def 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, 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 None
mid = l + (r - l) // 2
root = TreeNode(val=nums[mid])
root.left = self.traversal(nums, l, mid - 1)
root.right = self.traversal(nums, mid + 1, r)
return root
def 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, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def __init__(self):
self.pre = 0
def traversal(self, root):
if not root:
return
self.traversal(root.right)
root.val += self.pre
self.pre = root.val
self.traversal(root.left)
def convertBST(self, root):
"""
:type root: Optional[TreeNode]
:rtype: Optional[TreeNode]
"""
self.traversal(root)
return root
原文地址：https://blog.csdn.net/CSDN_dzh/article/details/144409975
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！