二叉树

LeetCode 树题大多基于二叉树的遍历和递归定义。先掌握前/中/后序和层序，再练递归写法和常见题型。

节点定义

树节点通常带 val、left、right；题目会给这种结构或数组（按层序存）。

前序、中序、后序（递归）

前序：根 → 左 → 右；中序：左 → 根 → 右；后序：左 → 右 → 根。递归写法最直观。

层序遍历（BFS）

用队列，每次处理一层，LeetCode 很多「按层」的题都用这个。

树高与判断平衡

树高递归：height = 1 + max(left_h, right_h)；平衡即左右高差 ≤ 1 且左右子树都平衡。

小结

• 遍历：前/中/后序用递归或栈，层序用队列。
• 递归：先想「当前节点做什么」「左右子树返回什么」再写边界 if not root。
• 很多题是「遍历 + 在遍历过程中记录/判断」（如最大深度、路径和、镜像等）。