C++ 笔试刷题实战：数字重排、队列约束与二叉树路径和

解题思路

这是一个典型的回溯问题。我们需要按位置依次填入队员，同时维护已使用状态和约束条件。

1. 使用 vis 数组记录队员是否已被安排。
2. 递归尝试将每个未使用的队员放入当前空位。
3. 关键剪枝：如果当前队员 i 的诉求对象 arr[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 在 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;
}

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

题目描述

给定一棵二叉树，求任意路径的最大路径和。路径定义为从任意节点出发，到达任意节点的序列，节点可向上或向下移动，但同一节点只能经过一次。路径至少包含一个节点。

解题思路

此题适合使用后序遍历（DFS）。对于每个节点，我们需要计算两个值：

1. 单侧最大路径和：以当前节点为起点，向左或向右延伸的最大路径和（用于返回给父节点）。
2. 全局最大路径和：以当前节点为转折点（即路径经过当前节点，连接左右子树）的最大和。

关键点在于处理负数。如果某条子路径的和小于 0，不如不选（相当于截断），因此取 max(0, 子路径和)。 更新全局最大值时，考虑左子树贡献 + 右子树贡献 + 当前节点值。 返回值时，只返回当前节点值 + max(左，右)，保证是单侧路径。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
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;
    }
};