二叉树详解：递归的艺术

大部分二叉树问题都可以分解为"处理当前节点 + 递归处理子树"

二叉树是我刷题过程中遇到最多的数据结构之一。刚开始觉得递归很绕，后来发现只要抓住"根-左-右"的思路，大部分问题都能迎刃而解。如果你对递归还不太熟悉，建议先画图，把每一步的调用栈写出来，会清晰很多。

什么是二叉树

二叉树是一种树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

1
2
3
4
5
    1          ← 根节点
   / \
  2   3        ← 左子节点、右子节点
 / \   \
4   5   6      ← 叶子节点（没有子节点）

节点定义

1
2
3
4
5
6
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

几个概念

术语 含义
根节点 树的最顶端节点
叶子节点 没有子节点的节点
深度 从根到该节点的边数
高度 从该节点到最远叶子的边数
层 深度相同的节点在同一层（从1开始）

二叉树的分类

graph TD
    A[二叉树] --> B[满二叉树]
    A --> C[完全二叉树]
    A --> D[二叉搜索树 BST]
    A --> E[平衡二叉树 AVL]
    
    style A fill:#FFE4B5
    style D fill:#90EE90
    style E fill:#87CEEB

满二叉树

每一层都是满的，节点数 = 2^h - 1（h是层数）

1
2
3
4
5
    1
   / \
  2   3
 / \ / \
4  5 6  7

完全二叉树

除了最后一层，其他层都是满的，且最后一层节点靠左排列。堆就是完全二叉树。

1
2
3
4
5
    1
   / \
  2   3
 / \
4   5

二叉搜索树（BST）

左子树所有节点 < 根 < 右子树所有节点。中序遍历是有序的。

1
2
3
4
5
6
7
        5
       / \
      3   7
     / \ / \
    2  4 6  8
    
中序遍历：2 3 4 5 6 7 8（有序！）

平衡二叉树

任意节点的左右子树高度差不超过1。

四种遍历方式

二叉树的遍历是基础中的基础，必须熟练掌握。

前序遍历（根-左-右）

1
2
3
4
5
6
void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";  // 先访问根
    preorder(root->left);       // 再遍历左子树
    preorder(root->right);      // 最后遍历右子树
}

中序遍历（左-根-右）

1
2
3
4
5
6
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);        // 先遍历左子树
    cout << root->val << " ";  // 再访问根
    inorder(root->right);       // 最后遍历右子树
}

后序遍历（左-右-根）

1
2
3
4
5
6
void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);      // 先遍历左子树
    postorder(root->right);     // 再遍历右子树
    cout << root->val << " ";  // 最后访问根
}

层序遍历（BFS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int size = q.size();
        vector<int> level;
        
        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        
        result.push_back(level);
    }
    
    return result;
}

遍历过程示例

1
2
3
4
5
6
7
8
9
10
        1
       / \
      2   3
     / \
    4   5

前序：1 2 4 5 3  （根-左-右）
中序：4 2 5 1 3  （左-根-右）
后序：4 5 2 3 1  （左-右-根）
层序：1 | 2 3 | 4 5

经典问题：最大深度

LeetCode 104: 给定一个二叉树，找出其最大深度。

递归解法

思路：树的最大深度 = max(左子树深度, 右子树深度) + 1

1
2
3
4
5
6
7
8
int maxDepth(TreeNode* root) {
    if (!root) return 0;
    
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    
    return max(leftDepth, rightDepth) + 1;
}

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
        3
       / \
      9  20
         / \
        15  7

调用 maxDepth(3)
├── 调用 maxDepth(9)
│   ├── maxDepth(null) = 0
│   └── maxDepth(null) = 0
│   └── 返回 max(0,0)+1 = 1
├── 调用 maxDepth(20)
│   ├── maxDepth(15) = 1
│   └── maxDepth(7) = 1
│   └── 返回 max(1,1)+1 = 2
└── 返回 max(1,2)+1 = 3

答案：3

时间复杂度：O(n)，每个节点访问一次
空间复杂度：O(h)，h是树的高度（递归栈）

经典问题：判断对称二叉树

LeetCode 101: 给定一个二叉树，检查它是否是镜像对称的。

思路

对称的条件：

  1. 根节点的值相等
  2. 左子树的左子树 = 右子树的右子树
  3. 左子树的右子树 = 右子树的左子树
1
2
3
4
5
    1
   / \
  2   2       ← 对称
 / \ / \
3  4 4  3     ← 对称

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    return isMirror(root->left, root->right);
}

bool isMirror(TreeNode* left, TreeNode* right) {
    if (!left && !right) return true;   // 都为空
    if (!left || !right) return false;  // 只有一个为空
    
    // 值相等，且子树对称
    return left->val == right->val
        && isMirror(left->left, right->right)
        && isMirror(left->right, right->left);
}

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
        1
       / \
      2   2
     / \ / \
    3  4 4  3

isMirror(2, 2)?
├── 2->val == 2->val ✓
├── isMirror(3, 3)?
│   ├── 3->val == 3->val ✓
│   ├── isMirror(null, null) = true
│   └── isMirror(null, null) = true
│   └── 返回 true
├── isMirror(4, 4)?
│   └── 返回 true
└── 返回 true

答案：true

经典问题：二叉树的最近公共祖先

LeetCode 236: 给定一个二叉树，找到两个节点的最近公共祖先（LCA）。

思路

递归查找 p 和 q：

  • 如果当前节点是 p 或 q，返回当前节点
  • 递归查找左右子树
  • 如果 p 和 q 分别在左右子树中，当前节点就是 LCA
  • 如果都在同一侧，返回那一侧的结果

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    // 递归终止条件
    if (!root || root == p || root == q) {
        return root;
    }
    
    // 在左右子树中查找
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    
    // p 和 q 分别在左右子树
    if (left && right) {
        return root;
    }
    
    // 都在某一侧
    return left ? left : right;
}

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

查找 p=5, q=4 的 LCA

LCA(3, 5, 4)
├── LCA(5, 5, 4)
│   └── root == p，返回 5
├── LCA(1, 5, 4)
│   ├── LCA(0, 5, 4) = null
│   └── LCA(8, 5, 4) = null
│   └── 返回 null
└── left=5, right=null，返回 5

答案：节点5

经典问题：二叉树的序列化与反序列化

LeetCode 297: 设计一个算法，将二叉树序列化为字符串，并能反序列化。

前序遍历方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Codec {
public:
    // 序列化
    string serialize(TreeNode* root) {
        if (!root) return "#";
        return to_string(root->val) + "," 
             + serialize(root->left) + "," 
             + serialize(root->right);
    }
    
    // 反序列化
    TreeNode* deserialize(string data) {
        queue<string> nodes;
        string token;
        for (char c : data) {
            if (c == ',') {
                nodes.push(token);
                token.clear();
            } else {
                token += c;
            }
        }
        nodes.push(token);
        return buildTree(nodes);
    }
    
private:
    TreeNode* buildTree(queue<string>& nodes) {
        string val = nodes.front();
        nodes.pop();
        
        if (val == "#") return nullptr;
        
        TreeNode* node = new TreeNode(stoi(val));
        node->left = buildTree(nodes);
        node->right = buildTree(nodes);
        return node;
    }
};

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
        1
       / \
      2   3
         / \
        4   5

序列化：1,2,#,#,3,4,#,#,5,#,#

反序列化过程：
1 → 创建节点1
2 → 创建节点2，作为1的左子节点
# → 2的左子节点为空
# → 2的右子节点为空
3 → 创建节点3，作为1的右子节点
4 → 创建节点4，作为3的左子节点
...

经典问题：从遍历结果构造二叉树

LeetCode 105: 根据前序遍历和中序遍历构造二叉树。

思路

1
2
前序：[3, 9, 20, 15, 7]  → 根-左-右，第一个是根
中序：[9, 3, 15, 20, 7]  → 左-根-右，根的左边是左子树
  1. 前序的第一个元素是根
  2. 在中序中找到根的位置，左边是左子树，右边是右子树
  3. 递归构造

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> inorderIndex;
    for (int i = 0; i < inorder.size(); ++i) {
        inorderIndex[inorder[i]] = i;
    }
    return build(preorder, 0, preorder.size() - 1,
                 inorder, 0, inorder.size() - 1, inorderIndex);
}

TreeNode* build(vector<int>& preorder, int preStart, int preEnd,
                vector<int>& inorder, int inStart, int inEnd,
                unordered_map<int, int>& inorderIndex) {
    if (preStart > preEnd) return nullptr;
    
    int rootVal = preorder[preStart];
    TreeNode* root = new TreeNode(rootVal);
    
    int rootIndex = inorderIndex[rootVal];
    int leftSize = rootIndex - inStart;
    
    root->left = build(preorder, preStart + 1, preStart + leftSize,
                       inorder, inStart, rootIndex - 1, inorderIndex);
    root->right = build(preorder, preStart + leftSize + 1, preEnd,
                        inorder, rootIndex + 1, inEnd, inorderIndex);
    
    return root;
}

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
前序：[3, 9, 20, 15, 7]
中序：[9, 3, 15, 20, 7]

Step 1: 根 = 3
        中序中 3 的位置 = 1
        左子树：前序[9], 中序[9]
        右子树：前序[20,15,7], 中序[15,20,7]

Step 2: 构造左子树，根 = 9
Step 3: 构造右子树，根 = 20
        ...

结果：
        3
       / \
      9  20
         / \
        15  7

经典问题：验证二叉搜索树

LeetCode 98: 判断一棵树是否是有效的二叉搜索树。

思路

利用 BST 的性质：中序遍历是严格递增的。

或者用递归：每个节点的值必须在一个合法范围内。

方法1：中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool isValidBST(TreeNode* root) {
    long long prev = LLONG_MIN;
    return inorderCheck(root, prev);
}

bool inorderCheck(TreeNode* node, long long& prev) {
    if (!node) return true;
    
    // 检查左子树
    if (!inorderCheck(node->left, prev)) return false;
    
    // 检查当前节点
    if (node->val <= prev) return false;
    prev = node->val;
    
    // 检查右子树
    return inorderCheck(node->right, prev);
}

方法2：递归范围检查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isValidBST(TreeNode* root) {
    return validate(root, LLONG_MIN, LLONG_MAX);
}

bool validate(TreeNode* node, long long minVal, long long maxVal) {
    if (!node) return true;
    
    if (node->val <= minVal || node->val >= maxVal) {
        return false;
    }
    
    return validate(node->left, minVal, node->val)
        && validate(node->right, node->val, maxVal);
}

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
        5
       / \
      1   4
         / \
        3   6

validate(5, -∞, +∞)
├── validate(1, -∞, 5) = true
├── validate(4, 5, +∞)
│   └── 4 不在 (5, +∞) 范围内！
│   └── 返回 false

答案：false（不是有效BST）

迭代遍历（非递归）

有时候面试官会要求用迭代方式实现遍历。

前序遍历（迭代）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    if (!root) return result;
    
    stack<TreeNode*> stk;
    stk.push(root);
    
    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        result.push_back(node->val);
        
        // 先压右，再压左（因为栈是后进先出）
        if (node->right) stk.push(node->right);
        if (node->left) stk.push(node->left);
    }
    
    return result;
}

中序遍历（迭代）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> stk;
    TreeNode* curr = root;
    
    while (curr || !stk.empty()) {
        // 一路向左
        while (curr) {
            stk.push(curr);
            curr = curr->left;
        }
        
        // 访问节点
        curr = stk.top();
        stk.pop();
        result.push_back(curr->val);
        
        // 转向右子树
        curr = curr->right;
    }
    
    return result;
}

常见技巧总结

1. 递归三要素

  1. 终止条件：if (!root) return ...
  2. 递归操作：处理当前节点
  3. 递归调用：处理左右子树

2. 遍历选择

场景 推荐遍历
求深度/高度 后序（先知道子树信息）
BST 相关 中序（有序性）
路径问题 前序（从上到下）
层级相关 层序（BFS）
序列化/反序列化 前序 + 标记空节点

3. 常见陷阱

1
2
3
4
5
6
7
8
9
10
11
// ❌ 错误：没有处理空节点
int maxDepth(TreeNode* root) {
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    // 当 root 为空时会崩溃！
}

// ✅ 正确：先判空
int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

思维导图

graph TD
    A[二叉树] --> B[基本概念]
    A --> C[遍历方式]
    A --> D[经典问题]
    
    B --> B1[节点定义]
    B --> B2[满/完全/BST]
    
    C --> C1[前序 根-左-右]
    C --> C2[中序 左-根-右]
    C --> C3[后序 左-右-根]
    C --> C4[层序 BFS]
    
    D --> D1[最大深度]
    D --> D2[对称二叉树]
    D --> D3[最近公共祖先]
    D --> D4[验证BST]
    D --> D5[序列化]
    
    style A fill:#FFE4B5
    style C fill:#90EE90
    style D fill:#87CEEB

总结

核心要点

  1. 递归是处理二叉树的核心：大部分问题都可以分解为"处理当前节点 + 递归处理子树"
  2. 掌握四种遍历：前序、中序、后序、层序，各有应用场景
  3. BST 的中序遍历是有序的：很多 BST 问题可以利用这个性质
  4. 空节点要先判断：递归的第一步往往是 if (!root) return ...

LeetCode 推荐题单

入门：

  • 104 最大深度
  • 101 对称二叉树
  • 226 翻转二叉树

进阶：

  • 102 层序遍历
  • 236 最近公共祖先
  • 105 前序+中序构造二叉树

挑战：

  • 124 二叉树最大路径和
  • 297 序列化与反序列化
  • 99 恢复BST

推荐阅读：