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

rhsgfswg

一、问题分析

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

二、解题思路

• ‌中序遍历序列‌：BST的中序遍历结果是一个严格递增序列
• ‌问题转化‌：将原二叉树的中序遍历序列转换为严格递增序列所需的最少修改次数
• ‌最长递增子序列(LIS)‌：最少修改次数 = 序列长度 - 最长递增子序列长度
  
  

三、C++代码实现

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. using namespACe std;
   
5. 
   
6. struct TreeNode {
   
7.     int val;
   
8.     TreeNode *left;
   
9.     TreeNode *right;
   
10.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    
11. };
    
12. 
    
13. // 构建二叉树
    
14. TreeNode* buildTree(int n, const vector<int>& vals, const vector<pair<int, int>>& edges) {
    
15.     vector<TreeNode*> nodes(n + 1);
    
16.     for (int i = 1; i <= n; ++i) {
    
17.         nodes[i] = new TreeNode(vals[i - 1]);
    
18.     }
    
19.    
    
20.     for (int i = 2; i <= n; ++i) {
    
21.         int fa = edges[i - 2].first;
    
22.         int ch = edges[i - 2].second;
    
23.         if (ch == 0) {
    
24.             nodes[fa]->left = nodes[i];
    
25.         } else {
    
26.             nodes[fa]->right = nodes[i];
    
27.         }
    
28.     }
    
29.     return nodes[1];
    
30. }
    
31. 
    
32. // 中序遍历收集节点值
    
33. void inorder(TreeNode* root, vector<int>& seq) {
    
34.     if (!root) return;
    
35.     inorder(root->left, seq);
    
36.     seq.push_back(root->val);
    
37.     inorder(root->right, seq);
    
38. }
    
39. 
    
40. // 计算最长递增子序列长度
    
41. int lengthOfLIS(vector<int>& nums) {
    
42.     vector<int> dp;
    
43.     for (int num : nums) {
    
44.         auto it = lower_bound(dp.begin(), dp.end(), num);
    
45.         if (it == dp.end()) {
    
46.             dp.push_back(num);
    
47.         } else {
    
48.             *it = num;
    
49.         }
    
50.     }
    
51.     return dp.size();
    
52. }
    
53. 
    
54. int main() {
    
55.     ios::sync_with_stdio(false);
    
56.     cin.tie(nullptr);
    
57.    
    
58.     int n;
    
59.     cin >> n;
    
60.    
    
61.     vector<int> vals(n);
    
62.     for (int i = 0; i < n; ++i) {
    
63.         cin >> vals[i];
    
64.     }
    
65.    
    
66.     vector<pair<int, int>> edges(n - 1);
    
67.     for (int i = 0; i < n - 1; ++i) {
    
68.         cin >> edges[i].first >> edges[i].second;
    
69.     }
    
70.    
    
71.     TreeNode* root = buildTree(n, vals, edges);
    
72.     vector<int> seq;
    
73.     inorder(root, seq);
    
74.    
    
75.     int lis_len = lengthOfLIS(seq);
    
76.     cout << n - lis_len << endl;
    
77.    
    
78.     return 0;
    
79. }

复制代码

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