任务
226. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
思路
逻辑上，我们知道用递归遍历一棵树，一定会遍历每个节点。因此在遍历的过程中处理即可。
- 考虑递归基，即当节点为空时直接返回。
- 考虑单层递归，为了反转二叉树，如何处理当前节点呢？即如何反转以当前节点为根的二叉树呢？ 交换其左右子节点，然后分别以左右孩子节点为根去反转（递归处理孩子节点）。
实际上这里的思路我们使用正好使用了类似先序遍历的流程，先处理当前节点的局部，再递归处理其孩子节点；实际上，如果在这里采用后序遍历的思路，也即是先让孩子节点为根去反转，再将自己的左右孩子反转。
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> 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
特别地，如果采用中序遍历，先以左孩子为根去反转，再交换左右孩子，此时就需要再以左孩子为根去反转了（因为此时左孩子已经是之前的右孩子了）
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root: return root
self.invertTree(root.left)
tmp = root.left
root.left = root.right
root.right = tmp
self.invertTree(root.left)
return root
实际上个人认为不用太区分树的遍历用递归时用的是什么序遍历，而是根据单次递归中需要的逻辑是什么去思考和编码即可，如果题目够复杂，你的遍历可能都不是单纯的处理一次，分不出先中后序。即处理时机可能在递归调用左右子节点的前中后多个部分。
101. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
思路
看到这道题，想到要遍历两棵树的过程中，判断这两棵树是否是对称的。这道题的递归基和单次递归逻辑联系的更紧密一些
- 如果这两棵树的树根均为空，则返回True
- 如果这两树的树根不同时为空，则返回False
- 如果这两树的树根均不为空，判断如下
- 如果两树根值不等，则返回False
- 如果两树根值相等，则判断它们的子树是否为对称（a的左子树是否和b的右子树对称，a的右子树是否和左子树对称），同时满足则返回True,否则返回False
class Solution:
def isSymmetricTwoTree(self,root1,root2):
if root1 and root2:
if root1.val != root2.val:
return False
else: # 值相等时，同时遍历两棵树的子树，确认是否对称
case1 = self.isSymmetricTwoTree(root1.left,root2.right)
case2 = self.isSymmetricTwoTree(root1.right,root2.left)
return case1 and case2
elif not root1 and not root2:
return True
# elif not root1 and root2 or (root1 and not root2):
# return False
else: return False
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
return self.isSymmetricTwoTree(root.left,root.right)
104.二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
思路
- 递归基：当前节点为空时，返回0
- 单层递归逻辑：当前节点的最大深度为，其左节点的最大深度和右节点最大深度中较大的加1.
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root: return 0
leftNum = self.maxDepth(root.left)
rightNum = self.maxDepth(root.right)
return max(rightNum,leftNum) + 1
111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
思路
大体思路和最大深度相同，但是直接将max改为min后，发现结果出错，一个只有右链的树返回的值是1，说明单层逻辑考虑的情况节点的左右孩子一边为空的时候按照之前的逻辑是不对的，因此需要特别处理，当某孩子一边为空，则返回另一孩子的最小深度。
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root: return 0
leftNum = self.minDepth(root.left)
rightNum = self. minDepth(root.right)
if not root.left and root.right: return rightNum + 1
elif root.left and not root.right: return leftNum + 1
return min(rightNum,leftNum) + 1
注意这最后两道题，最大深度和最小深度，用之前的层序遍历也可以实现。
- 最大深度用层序遍历的逻辑是，开始用res记录，每层加1，层序遍历完成后返回res
- 最小深度用层序遍历的逻辑是，用res记录，同样每层加1，但是如果提前碰到叶子节点，则直接返回res加1。
也即是说，用dfs和bfs都可以实现这两个功能，目前在二叉树章节中的理解是，dfs是用递归的逻辑去思考（递归基，单层递归逻辑），bfs是用层序遍历逻辑处理，也就是用层序遍历的那个队列二重循环的模板去处理。
心得体会
对于这种递归的题目，思考如何解时不要陷入到整个流程运作的细节，而是思考这样两个问题：
- 为了让递归不无限下分，边界条件是什么？也就是，递归基是什么？有了归基，我们知道递归可以有终点，会一层一层的返回给上层递归函数（类比循环中的终止条件是什么），此外，这个相当于我们针对边界的处理，比如节点为空时我们的题意的逻辑是什么？
- 单层递归时，为了实现逻辑，我们该怎么做？（类比循环中的单次循环中我们该做什么） 这个相当于是如果当前节点不是边界，我们的题意的逻辑是什么。