lc144.二叉树的中序遍历
题目链接
//to be updated
这个算法的时间复杂度是O（N），空间复杂度是O（N）。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
self.res = []
self.dfs(root)
...
lc101.对称二叉树
题目链接
这个算法的时间复杂度是O（N），空间复杂度是O（N）。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
return self.recur(root.lef...
lc055.跳跃游戏
题目链接
这题可以用贪心算法考虑。我们在遍历数组时，时刻维护一个“能跳到的最远的位置”，当在遍历过程中这个值大于等于数组长度-1时，说明能到达最后一个位置。若在遍历过程中，所维护的值比在判断的下标还要小时，说明该位置达不到，那更不可能达到比这个位置更远的位置，甚至最后一个位置。这个算法的时间复杂度是O（N），空间复杂度是O（1）。
class Solution:
def canJump1(self, nums: List[int]) -> bool:
n, rightmost = len(nums), 0
for i in range(n):
if i <= rightmost:
...
jz029.顺时针打印矩阵
题目链接
这个问题，再用将矩阵用图形表示出来之后更容易思考。我们可以注意到，打印矩阵的时候，我们可以将过程分解成一圈圈打印。那么有几层就有几次循环。那么如何判断矩阵里有几层圈圈呢，最关键的点在于坐上角的位置，因为这个位置不论矩阵形状如何，其坐标里的X，Y总是相等的，并且满足当循环没有终止时，该位置横坐标值的两倍小于矩阵列的数量，该位置纵坐标的
这个算法的时间复杂度是O（N），空间复杂度是O（N）。
class Solution:
def spiralOrder1(self, matrix: List[List[int]]) -> List[int]:
self.ans = []
if matrix == []:
...
jz028.对称的二叉树
题目链接
注意到，如果一棵树满足题目要求，则其前序遍历序列和其翻转后的前序遍历序列应该是完全相同的。按照这个思想，我们可以依次判断该树与其翻转的树的前序遍历序列值是否一直相等，也就是用常规的前根序遍历和先根后右节点后左节点遍历得到的序列是否相同。这个算法的时间复杂度是O（N），空间复杂度是O（N）。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymme...
jz027.二叉树的镜像
题目链接
这题一种做法是递归地交换左右子节点。这个算法的时间复杂度是O（N），空间复杂度是O（N）。或者用一个辅助栈来记录节点，这种方法的时间、空间复杂度也都为O（N）。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def mirrorTree1(self, root: TreeNode) -> TreeNode:
self.helper(r...
lc094.二叉树的中序遍历
题目链接
遍历二叉树，一般来说有三种解法，一是最简单的递归解法，二是迭代解法，三是莫里斯遍历。
//to be updated
这个算法的时间复杂度是O（N），空间复杂度是O（N）。
class Solution:
def inorderTraversal1(self, root: TreeNode) -> List[int]:
self.res = []
self.dfs(root)
return self.res
def dfs(self, root):
if not root:
return
self.dfs(root.left)
...
jz026.树的子结构
题目链接
对于这道题目，我们可以将解决过程分成两步：第一步，在树A中找到和B的根节点的值，这节点标为R；第二步，当找到入口时，再判断树A中以R为根节点的子树是不是包含和树B一样的结构。对于第一步这一外层的递归，终止条件是走到两棵树的叶节点时。对于第二步这一内层的递归，当B被遍历完时则说明整棵树B都是A的子树，否则，当A提前被遍历完或者A和B的某个节点不同时，为False。这个算法的时间复杂度是O（NM），因为先遍历树A占用O（N），而每次调用recur占用O（M）。空间复杂度是O（N），因为当两棵树都退化为链表时，递归调用深度最大。当N<=M时，遍历树A与递归判断的总递归深度为N；当N>M时，最差情况为遍历至树A的叶节点，此时总递归深度为N。其中N为A中节点数量，M为B中...
lc001.两数之和
题目链接
迷惑的我，做了好几次了还卡着好久，真的💊
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = {}
for key, value in enumerate(nums):
if dic.get(target - value) is not None:
return [key, dic[target-value]]
else:
dic[value] = key
lc079.单词搜索
单词搜索
这题与矩阵中的路径相同。另外补充一下一个比较常见的
这个算法的时间复杂度是$O（3^KMN）$，K，M，N分别为word的长度和矩阵的两个维度，MN是因为第一个字符有可能需要遍历矩阵的每个位置，3的K次是因为在从第二个字符开始，其每次搜索都只需要搜索3个位置甚至更少。空间复杂度取决于递归深度，是O（K）。
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
lrow, lcol = len(board), len(board[0])
visited = [[False]*lcol for _ in range...
260 post articles, 26 pages.