代码随想录总结

二叉树章节

前序遍历

def dfs(node):if node is None:returnres.append(node.val)dfs(node.left)dfs(node.right)

中序遍历

def dfs(node):if node is None:returndfs(node.left)res.append(node.val)dfs(node.right)

后序遍历

def dfs(node):if node is None:returndfs(node.left)dfs(node.right)res.append(node.val)

层序遍历

	levels = []def traverse(node, level):if not node:returnif len(levels) == level:levels.append([])levels[level].append(node.val)traverse(node.left, level + 1)traverse(node.right, level + 1)

除了遍历就是树的生成比较麻烦。
树的生成：从中序和后序遍历序列构造二叉树，最大二叉树、将有序数组转换为二叉搜索树。这三道题类似的，掌握差不多即可。

最大二叉树

参考的是代码随想录中遍历序列构造二叉树。

def backtrack(pro_nums):if len(pro_nums)==0:return Noneval=max(pro_nums)idx=pro_nums.index(val)root=TreeNode(val)if len(pro_nums)==1:return rootroot.left=backtrack(pro_nums[:idx])root.right=backtrack(pro_nums[idx+1:])return rootif len(nums)==0:return Nonereturn backtrack(nums)

二叉树的生成

用于Leetcode中代码的调试

class Node(object):def __init__(self, x):self.val = xself.left = Noneself.right = Nonedef generate_tree(vals):if len(vals) == 0:return Noneque = []  # 定义队列fill_left = True  # 由于无法通过是否为 None 来判断该节点的左儿子是否可以填充，用一个记号判断是否需要填充左节点for val in vals:node = Node(val) if val is not None else None  # 非空值返回节点类，否则返回 Noneif len(que) == 0:root = node  # 队列为空的话，用 root 记录根结点，用来返回que.append(node)elif fill_left:que[0].left = nodefill_left = False  # 填充过左儿子后，改变记号状态if node:  # 非 None 值才进入队列que.append(node)else:que[0].right = nodeif node:que.append(node)que.pop(0)  # 填充完右儿子，弹出节点fill_left = True  #return root

数组

螺旋矩阵

学习leetcode官方题解
对于每层，从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于 (top,left)，右下角位于 (bottom,right)，按照如下顺序遍历当前层的元素。

1. 从左到右遍历上侧元素，依次为 (top,left) 到 (top,right)。
2. 从上到下遍历右侧元素，依次为 (top+1,right) 到 (bottom,right)。
3. 如果 left<right 且 top<bottom，则从右到左遍历下侧元素，依次为 (bottom,right−1) 到
   (bottom,left+1)，以及从下到上遍历左侧元素，依次为 (bottom,left) 到 (top+1,left)。

遍历完当前层的元素之后，将 left 和 top 分别增加 1，将 right 和 bottom 分别减少 1，进入下一层继续遍历，直到遍历完所有元素为止。

		m = len(matrix)n = len(matrix[0])loop = max(m, n) // 2top,left,bottom,right=0,0,m-1,n-1result=[]while top<=bottom and left<=right:for i in range(left,right+1):result.append(matrix[top][i])for i in range(top+1,bottom+1):result.append(matrix[i][right])if top<bottom and left<right:for i in range(right-1,left,-1):result.append(matrix[bottom][i])for i in range(bottom,top,-1):result.append(matrix[i][left])left+=1top+=1right-=1bottom-=1return result

这种解法相对通解，适用于nn的正方形矩阵，也适用于mn的矩阵，且相对来说便于理解。