二叉树基础
二叉树术语、表示方式、递归结构、四种遍历（前/中/后/层序），以及两种常见解题视角（遍历 vs 分解）。
#resource / algorithm
#type / concept
#status / growing
#ds / tree
#algo / dfs
#algo / bfs
#algo / recursion
[!info] related notes 算法面试题型 MOC DFS / BFS / 回溯 递归 二叉树层序遍历 二叉树高频题
二叉树基础
二叉树是学习 DFS / BFS 的绝佳载体：
- 学二叉树：先学“对象长什么样”（节点结构、术语、层级关系）
- 学 DFS / BFS：再学“怎么在对象上走”（遍历顺序 / 队列 / 栈）
推荐学习路线：二叉树基础 -> 二叉树遍历 -> DFS/BFS -> 回溯/图搜索。
1) 树是什么
树是层级结构：有根节点（root），没有环；除根外每个节点只有一个父节点。
常见例子：目录树、组织架构、DOM。
2) 二叉树是什么
二叉树（Binary Tree）：每个节点最多两个孩子：left / right。
注意“最多两个”，不是必须两个。
3) 常见术语（刷题够用）
- 根节点（root）
- 父/子节点
- 叶子节点（leaf）：没有孩子的节点
- 子树（subtree）：某个节点 + 其所有后代
- 节点的度：孩子个数（0/1/2）
- 深度/层数：从根到节点经历的边数或层级（按题目定义即可）
- 高度：从节点到最远叶子的最长路径长度（同样按题目定义）
4) 二叉树的表示方式
4.1 链式存储（面试最常见）
节点通常长这样（Python）：
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right4.2 顺序存储（完全二叉树/堆常见）
数组下标 i：
left = 2*i + 1right = 2*i + 2
5) 二叉树的“递归结构”（最核心性质）
任何二叉树都可以看成：根节点 + 左子树 + 右子树。
所以很多问题天然是递归分解：
- 节点数：
count(root) = count(root.left) + count(root.right) + 1 - 高度：
height(root) = max(height(left), height(right)) + 1
对应代码（Python）：
def count(root):
if not root:
return 0
return count(root.left) + count(root.right) + 1
def height(root):
if not root:
return 0
return max(height(root.left), height(root.right)) + 16) 什么是遍历
遍历 = 按某种顺序访问树中每个节点一次。
树上的两大类遍历：
- DFS：前序/中序/后序（本质是“访问时机”不同）
- BFS：层序遍历（按层扩展）
7) DFS：前序 / 中序 / 后序
三者都属于 DFS，因为它们都在沿分支向下深入，直到空节点再回溯。
统一视角：
- 前序：进入节点时访问（根最先）
- 中序：左子树处理完时访问（根在中间）
- 后序：左右子树都处理完时访问（根最后）
模板（Python）：
def preorder(root):
if not root:
return
print(root.val)
preorder(root.left)
preorder(root.right)
def inorder(root):
if not root:
return
inorder(root.left)
print(root.val)
inorder(root.right)
def postorder(root):
if not root:
return
postorder(root.left)
postorder(root.right)
print(root.val)8) BFS：层序遍历
层序遍历是 BFS 在树上的体现：一层层从上到下、从左到右。
模板（Python）：
from collections import deque
def level_order(root):
if not root:
return
q = deque([root])
while q:
node = q.popleft()
print(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)按层处理要固定 size = len(q)，见：二叉树层序遍历。
9) 两种常见解题视角（非常重要）
9.1 遍历思维
“我怎么把整棵树走一遍，并在走的过程中做事？”
典型：收集节点、找路径、统计某类节点。
9.2 分解问题（递归分治）
“如果我已经知道左子树和右子树的答案，怎么合成当前答案？”
典型：高度、节点数、是否相同、是否平衡、LCA（部分写法）。
10) 初学最容易混的点
if not root: return是递归边界；空节点在树题里非常重要- “左子树”不是左边一个点，而是左孩子为根的整棵树
- 前/中/后序不要死记：前序根最先，中序根在中间，后序根最后
11) 入门题单（LeetCode 热题 100 优先）
路线 B（刷题型，建立直觉）：
补充：
- 二叉树的最小深度（111）