二叉树基础
每个节点最多两个孩子。高度 h 的树节点数最多 2^(h+1)-1。满/完全二叉树用数组下标存储：parent=i//2，left=2i+1，right=2i+2（0-index）。
深度优先遍历：
def inorder(root):
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
def inorder_iter(root):
st, cur, res = [], root, []
while cur or st:
while cur:
st.append(cur)
cur = cur.left
cur = st.pop()
res.append(cur.val)
cur = cur.right
return res
层序：队列 BFS，按层收集。
递归套路
定义 dfs(node) 返回值：高度、是否平衡、最大路径和、直径等。后序便于先拿左右子树信息再合并到根。
最近公共祖先（LCA）：若 p,q 分居根两侧则根为 LCA；否则递归左右子树，非空一侧继续。
二叉搜索树（BST）
支持 O(h) 查找、插入、删除；平衡 BST 为 O(log n)。验证 BST 不能只比较父子，需传递 (min, max) 范围：
def is_valid_bst(root, lo=float("-inf"), hi=float("inf")):
if not root:
return True
if not (lo < root.val < hi):
return False
return (
is_valid_bst(root.left, lo, root.val)
and is_valid_bst(root.right, root.val, hi)
)删除节点：无子/单子直接换；双子节点用中序后继（右子树最小）或前驱替换再删。
面试高频
| 题意 | 要点 | |---|---| | 第 K 小 | 中序计数 | | 范围查询 | BST 剪枝 | | 有序数组转 BST | 中序分治取中点 | | 序列化 | 前序 + null 标记 |
练习：94、98、230、235、108、124。画图标明子树返回值，再写递归边界 if not root: return ...。