最近想着系统地刷一些题，找了许多资料与课程，最终发现labuladong的刷题方案比较适合我，于是开始按照labuladong 的算法小抄开始刷题，希望自己能够坚持下来，要一直成长，加油。
226. 翻转二叉树翻转二叉树：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
# 核心思路就是递归反转左右子树就可以了
if not root:return
# 先让左右子树进行翻转
root.right, root.left = root.left, root.right
# 递归调用函数让他们翻转就行了
self.invertTree(root.left)
self.invertTree(root.right)
return root
题解如上，其实核心的点在于：只要把二叉树上的每一个节点的左右子节点进行交换，最后的结果就是完全翻转之后的二叉树。关键思路在于我们发现翻转整棵树就是交换每个节点的左右子节点，于是我们把交换左右子节点的代码放在了前序遍历的位置。
总结一下核心突破点：识别可以用哪一种遍历方式+具体要对节点进行什么操作。
我们按照这个思路继续来看几道题：
116. 填充每个节点的下一个右侧节点指针按照上面的思路，我们最重要的其实就是要找到对单个节点进行的操作。这里的核心处理逻辑是一个节点的next指针指向另一个节点，即：node1.next = node2，然后我们需要从根节点开始，把每一个的左右子树都进行这样的操作，但需要注意的是还有不同子树间节点的连接，也需要连接起来。【注意递归函数体上来就应该把递归返回的条件写出来】
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
#定义递归函数体
def connect_two_nodes(node1,node2):
# 递归返回条件不能忘
if not node1 or not node2: return
# 核心处理逻辑
node1.next = node2
# 对两个节点内部各自进行连接
connect_two_nodes(node1.left,node1.right)
connect_two_nodes(node2.left,node2.right)
# 对两个节点之间进行连接操作
connect_two_nodes(node1.right,node2.left)
if not root: return None
connect_two_nodes(root.left,root.right)
return root
是不是有点意思，再来一题练练手：
114. 二叉树展开为链表还是同样的套路，先思考我们要对一个节点做什么，再将这样的作法推广到其他节点上去。可以看到，其实是需要对每一个节点：把它的右子树断开接到左子树末尾上面去，需要注意的是，不需要对根节点做额外的操作，只需要作用于左右子树递归完成即可。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if not root:return
self.flatten(root.left)
self.flatten(root.right)
#保存拆分之前的右子树
right = root.right
# 左子树变成右子树
root.right = root.left
# 左子树置为空
root.left = None
# 找到左边子树（现在已经变为右子树了）的最后一个节点，将原先的右子树（临时变量right）连接到最后一个节点上去
while root.right:
root = root.right
# 原右子树连接到现在右子树的最后一个节点即可
root.right = right
我们继续：
654. 最大二叉树遇到这种提很容易思路有，但是转化为代码难，还是按照我们之前的套路，需要认定出来最小的子问题是要做什么。最小的子问题应该是，在一个区间范围内，找到区间内的最大值，然后以该值为根节点，构建树，对于该值的左右区间继续递归分别构建左右子树。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
def build(nums, l, r):
# 左右边界冲突就返回
if l > r:return None
# 取出最大的值以及及其索引
max_num = max(nums[l:r+1])
max_num_idx = nums.index(max_num)
# 构建根节点及其左右子树，左右子树递归左右区间出来
root = TreeNode(max_num)
root.left = build(nums, l, max_num_idx-1)
root.right = build(nums, max_num_idx+1, r)
return root
return build(nums, 0, len(nums)-1)
继续
105. 从前序与中序遍历序列构造二叉树来来来，还是按照基本思路来弄。搞清楚我们最小子问题要做啥，其实就是要根据前序遍历的结果确定根节点元素，然后根据中序遍历结果找到对应的左右子树对应的区间即可，所以我们需要至少四个参数传入：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def build(preorder, pre_l, pre_r, inorder, in_l, in_r):
# 确定递归截止条件
if pre_l > pre_r or in_l > in_r:return
# 通过前序遍历第一个节点，找到根节点
root_val = preorder[pre_l]
# 找到根节点在后序遍历list中的索引，以便切分
root_index_in = inorder.index(root_val)
# 构造树的根节点
root = TreeNode(root_val)
# 永远盯着递归函数的定义，不要盯着细节
# 画图确定索引，先可以确定后续遍历中的索引，再根据后续遍历中左子树的长度确定其他长度
root.left = build(preorder, pre_l+1 , pre_l+root_index_in-in_l,
inorder, in_l , root_index_in-1)
root.right = build(preorder, pre_l+root_index_in-in_l+1 ,pre_r,
inorder, root_index_in+1, in_r)
return root
# 调用套路
return build(preorder, 0, len(preorder)-1,
inorder, 0, len(inorder)-1)
同样的套路可以解决另外一道题：
106. 从中序与后序遍历序列构造二叉树根据上面的套路来即可，关键是找准对应的左右边界：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
#先把框架写出来，剩下的再填就行
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
def build(inorder, in_left, in_right,
postorder, post_left, post_right):
if in_left > in_right or post_left > post_right: return None
# 先找到根节点,一定要注意这个索引不是固定的0/-1
root_val = postorder[post_right]
# 再找到根节点元素在中序遍历中的索引
in_root_index = inorder.index(root_val)
# 构建树，先构建根节点
root = TreeNode(root_val)
# 再构建左右子树
size_len = in_root_index - in_left
root.left = build(inorder,in_left , in_root_index-1,
postorder,post_left , post_left+size_len-1)
root.right = build(inorder, in_root_index+1, in_right,
postorder,post_left+size_len , post_right-1)
return root
return build(inorder, 0, len(inorder)-1,
postorder, 0, len(postorder)-1)
一下子干了两题，爽吧，主要是需要根据左右子树长度区分边界。再看一题
652. 寻找重复的子树这道题，看似很让人头疼啊，不要慌，先想一想，我们要解决啥子问题。
子问题的核心是要将各个子树表示出来，这里我们用到了树序列化的方法，将子树表示成子字符串，作为hashmap的K，V即是对应出现的次数，如果出现次数达到2，则将对应的子树加入结果列表中：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
res = []
temp = {}
def traverse(root):
# 先进行子树的表示，进行子树的序列化，后序遍历的方式进行保存
if not root:return "#"
left = str(traverse(root.left))
right = str(traverse(root.right))
str_sub_tree = left + "," + right+ "," + str(root.val)
# 将所有的子树加入临时map中，若有重复的，则将对应子树加入结果list中，多次重复只加入一次
if str_sub_tree in temp:
temp[str_sub_tree] += 1
if temp[str_sub_tree] == 2:
res.append(root)
else:
temp[str_sub_tree] = 1
return str_sub_tree
traverse(root)
return res
由此我们引申出更大的一个篇章就是二叉树的序列化与反序列化。下一篇我们继续来探究。
