文档讲解：代码随想录
视频讲解：代码随想录
状态：完成4道题
整体思路：交换每一个节点的左右孩子
思考：使用哪种遍历方式？
建议使用前序或后序遍历（中序遍历比较绕）
前序遍历
# 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: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
root.left, root.right = root.right, root.left # 中
self.invertTree(root.left) # 左
self.invertTree(root.right) # 右
return root后序遍历
# 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: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
self.invertTree(root.left) # 左
self.invertTree(root.right) # 右
root.left, root.right = root.right, root.left # 中
return root
中序遍历
思考：中序遍历不是左中右吗，为什么这里是左中左？
因为中间左右节点进行了交换，所以原来的右节点是现在的左节点
# 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: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
self.invertTree(root.left) # 左
root.left, root.right = root.right, root.left # 中
self.invertTree(root.left) # 左
return root
递归：后序排序
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
return self.compare(root.left,root.right)
def compare(self,left,right):
# 对节点的数据进行过滤
if left == None and right != None:
return False
elif left != None and right == None:
return False
elif left ==None and right ==None:
return True
elif left.val != right.val:
return False
outside = self.compare(left.left,right.right)
inside = self.compare(left.right,right.left)
isSame = outside and inside
return isSame
深度：二叉树中任意节点到根节点的距离（取决于深度从0开始还是从1开始），求深度是从上往下计数
高度：二叉树中任意节点到叶子节点的距离（取决于高度从0开始还是从1开始），求高度是从上往下计数
根节点的高度就是二叉树的最大深度，所以这里我们使用后序遍历树的高度
递归三部曲：
1、确定递归函数的参数和返回值
def getDepth(node)2、确定终止条件
如果为空节点的话，就返回0，表示高度为0。
if not node:
return 03、确定单层递归的逻辑
先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。
leftheight = self.getDepth(node.left) # 左
rightheight = self.getDepth(node.right) # 右
height = 1 + max(leftheight,rightheight) # 中
return height# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
return self.getDepth(root)
def getDepth(self,node):
if not node:
return 0
leftheight = self.getDepth(node.left)
rightheight = self.getDepth(node.right)
height = 1 + max(leftheight,rightheight)
return height这里要注意题目要求：
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
根据题意可知，此题和求最大深度的题还是有很大区别的，这里的单层递归逻辑要考虑，左孩子为空和右孩子为空的情况，不要写成下面这样（按照下面代码的运行逻辑，返回的最小深度是1，是错误的）
leftheight = self.getDepth(node.left) # 左
rightheight = self.getDepth(node.right) # 右
height = 1 + max(leftheight,rightheight) # 中
return height正确写法，考虑左孩子为空和右孩子为空的情况
leftheight = self.getDepth(node.left)
rightheight = self.getDepth(node.right)
if node.left == None and node.right != None:
return 1 + rightheight
if node.left != None and node.right == None:
return 1 + leftheight
height = 1 + min(leftheight,rightheight)
return height# 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 minDepth(self, root: Optional[TreeNode]) -> int:
return self.getDepth(root)
def getDepth(self,node):
if not node:
return 0
leftheight = self.getDepth(node.left)
rightheight = self.getDepth(node.right)
if node.left == None and node.right != None:
return 1 + rightheight
if node.left ! = None and node.right == None:
return 1 + leftheight
height = 1 + min(leftheight,rightheight)
return height