二叉树

ZaynPei Lv6
  2025-10-09 22:00 2025-10-09 22:00 Created   2025-11-11 22:32:25 2025-11-11 22:32:25 Updated      3.6k Words  14 Mins

二叉树

二叉树是一种非常适合递归处理的数据结构, 因为每个节点都可以看作是一个子树的根节点.

必须回答的三个核心问题（递归的灵魂）

下面是二叉树递归的三个核心问题。每当你面对一个新的二叉树问题时，都要问自己这三个问题，从而设计出合适的递归函数。

递归边界：nullptr vs. 叶子节点？ - if (root == nullptr)（空节点边界） - 这是最常用、最健壮的边界, 几乎所有二叉树递归都应该使用它作为基础边界条件(但不一定是唯一边界条件)。 - 含义：“我这个递归函数被要求去处理一个不存在的节点，我什么也不用做，直接 return（或 return 0, return true 等默认值）。” - 优点：它能统一处理所有情况，包括： - 整个树为空（dfs(head) 一开始 head 就是 nullptr）。 - 一个节点只有左孩子（dfs(root->right) 时会触发）。 - 一个节点是叶子节点（dfs(root->left) 和 dfs(root->right) 都会触发）。 - if (root->left == nullptr && root->right == nullptr)（叶子节点边界） - 这是极少数情况，只在问题逻辑必须在“叶子”处终止时才使用, 但也需要额外加上 if (root == nullptr) 作为基础边界。 - 含义：“我这个 dfs 函数在到达子节点时，就要停止‘递’，开始‘归’。” - 典型案例： - (112. 路径总和)：你必须在叶子节点处判断 sum == targetSum，而不是在 nullptr 处。 - (404. 左叶子之和)：你必须从父节点判断 parent->left 是 一个叶子，才能累加。 - 结论：永远默认使用 if (root == nullptr) 作为递归边界。 只有当题目（如“路径总和”）明确要求你必须在叶子节点做判断时，才额外增加对叶子节点的判断。

返回类型: void vs. 有返回值？ - void dfs(…) (无返回值) - 含义：你不需要从子节点获取“答案”。 - 用途 1 (自顶向下)：父节点向子节点传递信息。比如 dfs(root, currentSum)，父节点把“当前的路径和”传给子节点。 - 用途 2 (外部变量)：你使用一个类成员变量或引用传递的变量来存储最终答案。 - void dfs(root, vector<int>& path, vector<vector<int>>& op), 或者是类成员变量 vector<vector<int>> results;。 - 在递归过程中不断更新 path，当到达叶子节点时，把 path 加入 results。 - 典型案例： - 回溯 (113. 路径总和 II)：你需要一个 path 变量一路传下去。 - 自顶向下 (129. 求根节点到叶节点数字之和)：dfs(root, currentNum * 10 + root->val)。 - T dfs(…) (有返回值，如 int, bool, TreeNode)
- 含义：父节点必须等到子节点的递归调用返回一个结果后，才能计算出父节点“自己”的结果。这是“自底向上”的核心。 - 典型案例： - (104. 二叉树的最大深度)： - int dfs(root) - int leftDepth = dfs(root->left); - int rightDepth = dfs(root->right); - return 1 + std::max(leftDepth, rightDepth); - (父节点的答案依赖于子节点的答案) - (110. 平衡二叉树)：int dfs(root)（返回高度，如果-1则表示不平衡）。 - (236. 最近公共祖先)：TreeNode dfs(root, …)（返回 p 或 q 或 nullptr）。 - 结论：问自己：“父节点的答案，是否依赖于子节点的计算结果？” - 是 → 有返回值 (自底向上)。 - 否 → void (自顶向下，或使用外部变量)。

自顶向下 (Top-Down) vs. 自底向上 (Bottom-Up)？ - 这是对上面“返回类型”的进一步理解。 - 自顶向下 (Pre-order / 先序遍历) - 执行顺序：1. 处理 root → 2. 递归 left → 3. 递归 right - 含义：“继承”——父节点处理完自己的逻辑，然后把信息传递给子节点。 - 代码模板 (104. 最大深度 - Top-Down 解法)： 

1
2
3
4
5
6
7
8
9
int maxDepth = 0; // 类成员变量或外部变量
void dfs(TreeNode* node, int currentDepth) {
    if (node == nullptr) {
        maxDepth = std::max(maxDepth, currentDepth);
        return;
    }
    dfs(node->left, currentDepth + 1);
    dfs(node->right, currentDepth + 1);
}
- 自底向上 (Post-order / 后序遍历) - 执行顺序：1. 递归 left (拿结果) → 2. 递归 right (拿结果) → 3. 处理 root (汇总) - 含义：“聚合”——父节点必须等待左右子树的结果，才能计算出自己的结果。 - 代码模板 (104. 最大深度 - Bottom-Up 解法)： 
1
2
3
4
5
6
7
8
int dfs(TreeNode* node) {
    if (node == nullptr) {
        return 0;
    }
    int leftDepth = dfs(node->left);
    int rightDepth = dfs(node->right);
    return 1 + std::max(leftDepth, rightDepth);
}
- 一般来说，自底向上更常见，因为大多数二叉树问题都需要汇总子节点的结果来计算父节点的答案。 - 结论：问自己：“父节点的答案，是否依赖于子节点的计算结果？” - 是 → 自底向上 (有返回值)。 - 否 → 自顶向下 (void 或外部变量)。

二叉树的遍历

二叉树的遍历主要有三种方式: 前序遍历 (Preorder), 中序遍历 (Inorder), 后序遍历 (Postorder). 这三种遍历方式的区别在于访问节点的顺序不同, 名称反映的是访问根节点的时机

三种遍历都可以使用递归实现, 较为简单. 例如:

1
2
3
4
5
6
7
8
9
10
// 前序遍历 (根-左-右)
void preorder(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    // 访问根节点
    result.push_back(root->val);
    // 遍历左子树
    preorder(root->left, result);
    // 遍历右子树
    preorder(root->right, result);
}

使用迭代实现时, 通常需要借助栈 (Stack) 来手动模拟递归调用栈的行为.

迭代遍历

对于前序遍历, 迭代实现相对简单, 只需要一个栈来辅助即可.

不过需要注意的是, 前序遍历中, 我们需要先将右子节点入栈, 再将左子节点入栈, 这样才能保证左子节点先被访问.(访问顺序和入栈顺序相反) 

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
std::vector<int> preorderIterative(TreeNode* root) {
    std::vector<int> result;
    if (root == nullptr) {
        return result;
    }

    std::stack<TreeNode*> s;
    s.push(root); // 1. 首先将根节点入栈

    while (!s.empty()) {
        TreeNode* node = s.top(); // 2. 取出栈顶元素
        s.pop();
        result.push_back(node->val); // 3. 访问该节点（根）

        // 4. 关键：先将 右 子节点入栈，再将 左 子节点入栈
        // 这样能确保 左 子节点在 右 子节点之前被访问
        if (node->right != nullptr) {
            s.push(node->right);
        }
        if (node->left != nullptr) {
            s.push(node->left);
        }
    }
    return result;
}

对于后序遍历, 迭代实现相对复杂一些, 因为我们需要确保根节点在左右子节点之后被访问. 这里有两种常见的做法: 1. 将后序遍历转换为“根-右-左”的前序遍历, 然后再将结果反转. 2. 使用一个栈和一个指针: 通过一个指针来追踪上一个访问的节点, 以判断当前节点的右子树是否已经被访问过. 这里我们展示第二种方法: 

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
std::vector<int> postorderIterative(TreeNode* root) {
    std::vector<int> result;
    if (root == nullptr) {
        return result;
    }

    std::stack<TreeNode*> s;
    TreeNode* curr = root;
    TreeNode* lastVisited = nullptr; // 记录上一个访问的节点

    while (curr != nullptr || !s.empty()) {
        // 1. 一直向左走, 将路径上的节点入栈
        while (curr != nullptr) {
            s.push(curr);
            curr = curr->left;
        }

        // 2. 查看栈顶节点
        TreeNode* node = s.top();

        // 3. 判断右子树是否已经访问过
        if (node->right == nullptr || node->right == lastVisited) {
            // 如果没有右子树或右子树已经访问过, 则访问当前节点
            result.push_back(node->val);
            s.pop();
            lastVisited = node; // 更新上一个访问的节点
            curr = nullptr; // 防止再次进入左子树
        } else {
            // 如果有右子树且未访问过, 则转向右子树
            curr = node->right;
        }
    }
    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
24
25
26
27
std::vector<int> postorderIterative(TreeNode* root) {
    std::vector<int> result;
    if (root == nullptr) {
        return result;
    }

    std::stack<TreeNode*> s;
    s.push(root);

    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        result.push_back(node->val); // 先访问根节点

        // 先将左子节点入栈, 再将右子节点入栈
        if (node->left != nullptr) {
            s.push(node->left);
        }
        if (node->right != nullptr) {
            s.push(node->right);
        }
    }

    // 最后反转结果以获得后序遍历顺序
    std::reverse(result.begin(), result.end());
    return result;
}

对于中序遍历, 我们需要模拟“一路向左，直到尽头；访问；然后转向右子树”的过程。

  • 使用一个 curr 指针指向当前节点，初始为 root。
  • 外层循环：只要 curr 不为空 或 栈不为空，就继续。
    • 步骤 A (深入左子树)：while (curr != nullptr)：只要当前节点不为空，说明它有（或它就是）一个需要稍后访问的“根”。
      • 将其入栈（表示“我稍后会回来访问你”）。
      • curr = curr->left;（继续深入左子树）。
    • 步骤 B (访问根并转向右)：当 while 循环结束时，curr 必定为空，表示我们已到达最左侧的尽头。
      • 此时从栈中弹出一个节点（这个节点是“左-根-右”中的根）。
      • 访问它（加入结果列表）。
      • curr = popped_node->right;（将 curr 指针转向该节点的右子树，准备在下一轮外层循环中处理右子树）。 
        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
        std::vector<int> inorderIterative(TreeNode* root) {
            std::vector<int> result;
            
            std::stack<TreeNode*> s;
            TreeNode* curr = root; // 使用一个指针来追踪当前节点

            // 循环条件：当前节点不为空（表示还有子树待处理）
            // 或者 栈不为空（表示还有已入栈的父节点待访问）
            while (curr != nullptr || !s.empty()) {
                
                // 1. 深入左子树：不断将当前节点入栈，并向左下方移动
                // 直到 curr 为空，表示到达了最左侧
                while (curr != nullptr) {
                    s.push(curr);       // 将路径上的“根”节点入栈
                    curr = curr->left;
                }

                // 2. 访问根节点：当curr为空时，从栈中弹出节点
                // 这是"左-根-右"中的"根"，也是最左侧的节点
                curr = s.top();
                s.pop();
                result.push_back(curr->val); // 访问根节点

                // 3. 转向右子树：将当前节点指向右子树
                // 在下一轮循环中，将对这个右子树重复“步骤1”
                curr = curr->right;
            }
            return result;
        }

层序遍历 (Level-order)

还有一种遍历是层序遍历 (Level-order), 也称为广度优先遍历 (BFS). 这是唯一的主流非递归解法。当你需要按层处理问题时，BFS 是首选。

层序遍历通常使用队列 (Queue) 来实现, 通过逐层访问节点来实现. 实现代码如下: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> results;
        if(!root) return results;

        queue<TreeNode*> que;  // 使用队列来辅助层序遍历
        que.push(root);
        while(!que.empty()){  // 每层循环处理一层节点, 由上一层节点入队列
            int size = que.size();
            vector<int> path;
            for(int i=0;i<size;i++){  // 处理当前层的所有节点
                TreeNode* node = que.front();
                path.push_back(node->val);
                que.pop();
                if(node->left) que.push(node->left);  // 将下一层节点入队列
                if(node->right) que.push(node->right);
            }
            results.push_back(path);
        }
        return results;
    }
};
### 二叉搜索树 (BST)

特点是: 对于每个节点, 左子树的所有节点值都小于该节点值, 右子树的所有节点值都大于该节点值.

一般使用中序遍历来处理二叉搜索树的问题, 因为中序遍历会得到一个有序序列.

最近公共祖先 (LCA)

最近公共祖先问题是二叉树中一个经典问题, 其核心思想是使用递归来查找两个节点的公共祖先. 这是一个经典的自底向上 (后序遍历) 递归。(LC 236) - dfs(root, p, q) 函数的语义（返回值）是：“在以 root 为根的子树中，我能找到 p 还是 q 还是它俩的 LCA？” - 如果找到了 p 或 q，返回对应的节点指针。 - 如果找到了 LCA，返回 LCA 节点指针。 - 如果都没找到，返回 nullptr。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    // 1. 边界: 空节点，或找到了 p 或 q
    if (root == nullptr || root == p || root == q) {
        return root;
    }

    // 2. 递归 left (拿结果)
    TreeNode* left_result = lowestCommonAncestor(root->left, p, q);

    // 3. 递归 right (拿结果)
    TreeNode* right_result = lowestCommonAncestor(root->right, p, q);

    // 4. 处理 root (汇总)
    // 解释: p 和 q 分布在 root 的两侧，
    // 那么 root 就是 LCA
    if (left_result != nullptr && right_result != nullptr) {
        return root;
    }else if (left_result != nullptr) { // 只有左子树找到了 p 或 q
        return left_result;  // 返回左子树的结果, 可能是 p, q, 或 LCA
    } else {
        return right_result;
    }
}

从…构造二叉树

从前序和中序遍历构造二叉树是一个经典问题, 其核心思想是利用前序遍历确定根节点, 然后利用中序遍历划分左右子树. (LC 105)

从前序和中序遍历构造二叉树

  • 先序遍历 (Preorder): [ 根节点, [左子树…], [右子树…] ]
    • preorder 数组的第一个元素（preorder[0]）永远是整棵树的根节点 (Root)。
  • 中序遍历 (Inorder): [ […左子树…], 根节点, […右子树…] ]
    • inorder 数组中根节点 (Root) 的位置，恰好划分了哪些节点属于左子树，哪些节点属于右子树。
    • 根节点左边的所有元素都在左子树, 根节点右边的所有元素都在右子树。
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
unordered_map<int, int> inorderMap; // (步骤说明)：一个全局索引，用于追踪先序遍历数组
int preorderIndex;  // 它始终指向下一个将被用作“根”的元素

TreeNode* buildTreeHelper(const vector<int>& preorder, int inorderLeft, int inorderRight) {
    // (步骤说明)：Base Case: 
    // 如果左边界大于右边界，说明中序遍历的窗口为空，
    // 这是一个空子树。
    if (inorderLeft > inorderRight) {
        return nullptr;
    }

    // --- 1. 找到并创建根节点 ---
    
    // (步骤说明)：根据先序遍历的性质，preorderIndex 指向的
    // 元素就是当前子树的根节点。
    int rootVal = preorder[preorderIndex];
    
    // (步骤说明)：将 preorderIndex 后移，
    // 准备为接下来的左子树或右子树提供根节点。
    preorderIndex++;
    
    TreeNode* root = new TreeNode(rootVal);

    // --- 2. 划分左右子树 ---
    
    // (步骤说明)：使用哈希表 O(1) 查找到根节点在中序遍历中的位置
    int inorderRootIndex = inorderMap[rootVal];
    
    // --- 3. 递归构建左右子树 ---
    
    // (步骤说明)：递归构建左子树
    // 左子树的中序遍历范围是 [inorderLeft, inorderRootIndex - 1]
    root->left = buildTreeHelper(preorder, inorderLeft, inorderRootIndex - 1);
    
    // (步骤说明)：递归构建右子树
    // 右子树的中序遍历范围是 [inorderRootIndex + 1, inorderRight]
    root->right = buildTreeHelper(preorder, inorderRootIndex + 1, inorderRight);

    // (步骤说明)：返回构建完成的根节点
    return root;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    // (步骤说明)：初始化先序遍历的索引，从 0 (第一个元素) 开始
    preorderIndex = 0;
    
    // (步骤说明)：构建中序遍历的 (值 -> 索引) 映射， O(n)
    for (int i = 0; i < inorder.size(); ++i) {
        inorderMap[inorder[i]] = i;
    }

    // (步骤说明)：启动递归
    // 初始的中序遍历窗口是整个数组 [0, n-1]
    return buildTreeHelper(preorder, 0, inorder.size() - 1);
}
On this page
二叉树
  1. 二叉树
    1. 必须回答的三个核心问题（递归的灵魂）
    2. 二叉树的遍历
      1. 迭代遍历
      2. 层序遍历 (Level-order)
    3. 最近公共祖先 (LCA)
    4. 从…构造二叉树
      1. 从前序和中序遍历构造二叉树