C++ 求解二叉树优美 DFS 序数量问题

以下是解决该问题的 C++ 代码： ```cpp #include <iostream> #include <vector> #include <stack> #define MOD 1000000007 using namespace std; // 定义二叉树节点结构体 struct TreeNode { int left; int right; TreeNode(int l, int r) : left(l), right(r) {} }; // 生成所有可能的 DFS 序 void generateDFS(vector<int>& path, vector<TreeNode>& tree, int node, vector<vector<int>>& dfs_orders) { if (node * 2 > tree.size()) { dfs_orders.push_back(path); return; } path.push_back(node); generateDFS(path, tree, tree[node - 1].left, dfs_orders); generateDFS(path, tree, tree[node - 1].right, dfs_orders); path.pop_back(); } // 判断一个 DFS 序是否优美 bool isBeautiful(const vector<int>& dfs_order, const vector<int>& leaf_values) { stack<int> st; for (int node : dfs_order) { if (node * 2 > leaf_values.size()) { if (!st.empty() && st.top() == leaf_values[node - 1]) { st.pop(); } else { st.push(leaf_values[node - 1]); } } } return st.empty(); } int main() { int c, n; cin >> c >> n; vector<TreeNode> tree(2 * n - 1, {0, 0}); for (int i = 0; i < 2 * n - 1; ++i) { int l, r; cin >> l >> r; tree[i] = TreeNode(l, r); } vector<int> leaf_values(4 * n - 1, 0); for (int i = 0; i < n; ++i) { int a, b; cin >> a >> b; leaf_values[a - 1] = i + 1; leaf_values[b - 1] = i + 1; vector<vector<int>> dfs_orders; vector<int> path; generateDFS(path, tree, 1, dfs_orders); int beautiful_count = 0; for (const auto& order : dfs_orders) { if (isBeautiful(order, leaf_values)) { beautiful_count = (beautiful_count + 1) % MOD; } } cout << beautiful_count << endl; } return 0; } ``` ### 代码解释： 1. **TreeNode 结构体**：用于表示二叉树的节点，包含左右子节点的编号。 2. **generateDFS 函数**：递归生成所有可能的 DFS 序。 3. **isBeautiful 函数**：判断一个 DFS 序是否优美，通过栈来模拟消除相邻相同数字的过程。 4. **main 函数**：读取输入数据，进行操作，并计算每次操作后的优美 DFS 序的数量。 ### 复杂度分析： - **时间复杂度**：生成所有 DFS 序的时间复杂度为 $O(2^{2n - 1})$，判断每个 DFS 序是否优美的时间复杂度为 $O(4n - 1)$，因此总的时间复杂度为 $O(2^{2n - 1} \times (4n - 1))$。 - **空间复杂度**：主要用于存储 DFS 序，空间复杂度为 $O(2^{2n - 1} \times (4n - 1))$。 ######[AI问答 | 884点数解答 | 2026-06-09 14:06:43]