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

二、体操队形

题目描述

队长需要对 n 名同学进行排队。第 i 号队员有一个诉求 a[i]，表示 i 必须排在 a[i] 的前面。若 a[i] == i，则表示无特殊要求。求一共有多少种合法的排队方案。

解题思路

这是一个典型的回溯问题。我们需要依次确定每个位置的人选，同时满足前驱约束条件。

核心逻辑在于：当尝试将队员 i 放入当前空位时，需要检查两个条件：

1. 队员 i 是否已经被安排过？
2. 队员 i 的诉求对象 a[i] 是否已经排好队了？如果 a[i] 已排且不在 i 之前，则此路不通。

我们使用一个 vis 数组记录已排人员，递归尝试填充每一个位置。当所有位置填满时，方案数加一。

#include <iostream>
using namespace std;

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

// pos: 当前要填充的位置索引
void dfs(int pos) {
    if (pos == n + 1) {
        ret++;
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue; // 该队员已排过
        
        // 如果该队员的诉求对象已排过，但不在该队员前面，则不满足条件
        // 注意：这里假设 a[i] 是 i 必须排在它前面的那个人
        if (arr[i] != i && 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 或 DFS 问题。关键在于理解'路径'的定义：它可以是单向的（如左子树 -> 根），也可以是分叉的（左子树 -> 根 -> 右子树）。

我们在遍历每个节点时，需要计算两个值：

1. 以当前节点为最高点的路径和：即 left_max + root->val + right_max。这用于更新全局最大值 ret。
2. 从当前节点向下延伸的单侧最大路径和：即 root->val + max(left_max, right_max)。这是递归返回值，供父节点使用。

注意：如果某棵子树的最大单路径和小于 0，说明该子树对总和有负贡献，此时应视为 0（即不选择该子树）。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ret = -100000000;

    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;
    }
};