力扣热门题解析（Python实现 36-40 题）
36、二叉树中序遍历
给定一个二叉树的根节点，返回其 中序遍历 结果。
- 输入：root = [1,null,2,3] → 输出：[1,3,2]
- 输入：root = [] → 输出：[]
- 输入：root = [1] → 输出：[1]
解法思路：采用递归方式，按"左子树 → 根节点 → 右子树"顺序访问节点。
def inorder_traversal(root: Optional[TreeNode]) -> List[int]:
result = []
def traverse(node):
if not node:
return
traverse(node.left)
result.append(node.val)
traverse(node.right)
traverse(root)
return result
37、二叉树的最大深度
求从根节点到最远叶节点的最长路径上的节点数量。
- 输入：root = [3,9,20,null,null,15,7] → 输出：3
- 输入：root = [1,null,2] → 输出：2
解法思路：递归计算左右子树的深度，取较大值加一。
def max_depth(root: Optional[TreeNode]) -> int:
if not root:
return 0
left_max = max_depth(root.left)
right_max = max_depth(root.right)
return max(left_max, right_max) + 1
38、翻转二叉树
将二叉树的所有左右子树互换位置。
- 输入：root = [4,2,7,1,3,6,9] → 输出：[4,7,2,9,6,3,1]
- 输入：root = [] → 输出：[]
解法思路：递归交换每个节点的左右子树。
def invert_tree(root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
root.left, root.right = root.right, root.left
invert_tree(root.left)
invert_tree(root.right)
return root
39、判断二叉树是否对称
检查一棵二叉树是否关于根节点轴对称。
- 输入：root = [1,2,2,3,4,4,3] → 输出：true
- 输入：root = [1,2,2,null,3,null,3] → 输出：false
解法思路：使用辅助函数比较两棵子树是否镜像对称：左子树的左子与右子树的右子、左子树的右子与右子树的左子需同时对称。
def is_symmetric(root: Optional[TreeNode]) -> bool:
def check_mirror(left_node, right_node):
if not left_node and not right_node:
return True
if not left_node or not right_node:
return False
return (left_node.val == right_node.val) and \
check_mirror(left_node.left, right_node.right) and \
check_mirror(left_node.right, right_node.left)
return check_mirror(root.left, root.right) if root else True
40、二叉树的直径
求任意两个节点之间的最长路径边数，该路径可能经过根节点也可能不经过。
- 输入：root = [1,2,3,4,5] → 输出：3
- 输入：root = [1,2] → 输出：1
解法思路：对每个节点，计算其左右子树的深度之和，作为以该节点为"最高点"的路径长度，并用全局变量维护最大值。
def diameter_of_binary_tree(root: Optional[TreeNode]) -> int:
max_diameter = 0
def get_depth(node):
nonlocal max_diameter
if not node:
return 0
left_height = get_depth(node.left)
right_height = get_depth(node.right)
current_path = left_height + right_height
max_diameter = max(max_diameter, current_path)
return 1 + max(left_height, right_height)
get_depth(root)
return max_diameter
