洛谷P3365 改造二叉树：从问题分析到代码实现

15303105423 · 发表于 3 天前

一、问题分析

题目要求我们计算将二叉树修改为二叉搜索树(BST)所需的最少修改次数。二叉搜索树的性质是：对于任意节点，其左子树所有节点的值都小于该节点的值，右子树所有节点的值都大于该节点的值。

二、解题思路

三、C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespACe std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 构建二叉树
TreeNode* buildTree(int n, const vector<int>& vals, const vector<pair<int, int>>& edges) {
vector<TreeNode*> nodes(n + 1);
for (int i = 1; i <= n; ++i) {
nodes[i] = new TreeNode(vals[i - 1]);
}
for (int i = 2; i <= n; ++i) {
int fa = edges[i - 2].first;
int ch = edges[i - 2].second;
if (ch == 0) {
nodes[fa]->left = nodes[i];
} else {
nodes[fa]->right = nodes[i];
}
}
return nodes[1];
}
// 中序遍历收集节点值
void inorder(TreeNode* root, vector<int>& seq) {
if (!root) return;
inorder(root->left, seq);
seq.push_back(root->val);
inorder(root->right, seq);
}
// 计算最长递增子序列长度
int lengthOfLIS(vector<int>& nums) {
vector<int> dp;
for (int num : nums) {
auto it = lower_bound(dp.begin(), dp.end(), num);
if (it == dp.end()) {
dp.push_back(num);
} else {
*it = num;
}
}
return dp.size();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> vals(n);
for (int i = 0; i < n; ++i) {
cin >> vals[i];
}
vector<pair<int, int>> edges(n - 1);
for (int i = 0; i < n - 1; ++i) {
cin >> edges[i].first >> edges[i].second;
}
TreeNode* root = buildTree(n, vals, edges);
vector<int> seq;
inorder(root, seq);
int lis_len = lengthOfLIS(seq);
cout << n - lis_len << endl;
return 0;
}

复制代码

五、总结

通过将问题转化为中序遍历序列的最长递增子序列问题，我们能够高效地计算出将任意二叉树修改为BST所需的最少修改次数。这种方法结合了树遍历和动态规划的思想，展示了算法设计中问题转化的重要性。