C++ 算法刷题实战：重组偶数、排队方案与二叉树路径和

二、体操队形

题目描述

队长需要对 n 名队员（编号 1 ~ n）进行排队。第 i 号队员有一个诉求 a[i]，表示 i 必须排在 a[i] 的前面。若 a[i] == i 则表示无特殊诉求。求合法的排队方案总数。

思路解析

这是一个典型的回溯（DFS）问题。我们需要按位置依次填入队员，同时满足约束条件。

1. 使用 vis 数组记录每个队员是否已被安排。
2. 在填充第 pos 个位置时，遍历所有未使用的队员 i。
3. 关键约束检查：如果队员 i 的诉求对象 arr[i] 已经被安排了（即 vis[arr[i]] 为真），且 arr[i] 不是当前正在填的位置，那么 i 就不能放在当前位置，因为 i 必须在 arr[i] 之前，而 arr[i] 已经在前面的位置了，这会导致冲突。
4. 递归尝试下一个位置，回溯时恢复状态。

代码实现

#include <iostream>
using namespace std;

int arr[11];      // 存储每个队员的诉求
bool vis[11];     // 记录队员是否已排入队列
int ret = 0;      // 方案总数
int n;            // 队员数量

void dfs(int pos) {
    if (pos == n + 1) {
        ret++;
        return;
    }
    
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue; // 队员 i 已用过
        
        // 如果队员 i 的诉求对象 arr[i] 已经排过队了，
        // 意味着 arr[i] 在 i 前面，违反 i 必须在 arr[i] 前面的规则
        if (vis[arr[i]]) return;
        
        vis[i] = true;
        dfs(pos + 1);
        vis[i] = false; // 回溯
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    dfs(1);
    cout << ret << endl;
    return 0;
}

三、二叉树中的最大路径和

题目描述

给定一棵二叉树，找出任意路径的最大路径和。路径定义为从任意节点出发，到达任意节点的序列，同一节点在路径中最多出现一次。路径至少包含一个节点。

思路解析

这道题是经典的树形 DP 或递归问题。核心在于区分'经过当前节点的最大路径和'与'从当前节点向下延伸的最大单路径和'。

1. 返回值定义：函数应返回以当前节点为起点，向下延伸的单侧路径最大和（用于父节点计算）。
2. 全局更新：在遍历过程中，计算以当前节点为转折点（连接左右子树）的路径和，并更新全局最大值。
3. 负值处理：如果左子树或右子树提供的路径和小于 0，则不应选择该分支（相当于截断），此时贡献值为 0。

注意：很多初学者容易忽略负值情况，导致当一侧子树和为负时仍强行相加，从而得到错误结果。正确的做法是对左右子树的返回值先取 max(0, val)。

代码实现

class Solution {
public:
    int ret = -1010;

    int dfs(TreeNode* root) {
        if (root == nullptr) return 0;
        
        // 获取左右子树的最大单路径和，若为负则取 0
        int left = max(dfs(root->left), 0);
        int right = max(dfs(root->right), 0);
        
        // 更新全局最大路径和（当前节点作为转折点）
        ret = max(ret, root->val + left + right);
        
        // 返回当前节点向下延伸的最大单路径和
        return root->val + max(left, right);
    }

    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ret;
    }
};

以上三个题目涵盖了字符串处理、回溯搜索以及树形递归，是笔试中常见的考点。理解每种场景下的核心约束与状态转移逻辑，比单纯记忆代码更重要。