题目

题解

在力扣 题目98- 验证二叉搜索树中 我们知道了 中序遍历后的二叉搜索树 应该为递增 那么出错就应该是有部分递减 那么我们在98题的基础上 反向检测 保存减少数列的开头与结尾进行交换

代码

 1 #include<iostream>
 2 #include<vector>
 3 #include<stack>
 4 using namespace std;
 5 
 6 
 7 struct TreeNode {
 8     int val;
 9     TreeNode* left;
10     TreeNode* right;
11     TreeNode() : val(0), left(nullptr), right(nullptr) {}
12     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
13     TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
14 };
15 //遍历
16 //即减少序列的第一个数与最后一个数交换
17 class Solution {
18 public:
19     void recoverTree(TreeNode* root) {
20         TreeNode* last = new TreeNode(INT_MAX);
21         TreeNode* max = new TreeNode(INT_MAX);
22         TreeNode* min = new TreeNode(INT_MAX);
23         stack<TreeNode*> ergodic;
24         while (root != nullptr || !ergodic.empty()) {
25             if (root != nullptr) {
26                 ergodic.push(root);
27                 root = root->left;
28             }
29             else
30             {
31                 if (ergodic.top()->val < last->val) {
32                     if (max->val == INT_MAX) {
33                         max = last;
34                     }
35                     min = ergodic.top();
36                 }
37                 last = ergodic.top();
38                 root = ergodic.top()->right;
39                 ergodic.pop();
40             }
41         }
42         swap(max->val, min->val);
43     }
44 
45     vector<int> inorderTraversal(TreeNode* root) {
46         vector<int> result;
47         stack<TreeNode*> ergodic;
48         while (root != nullptr || !ergodic.empty()) {
49             if (root != nullptr) {
50                 ergodic.push(root);
51                 root = root->left;
52             }
53             else
54             {
55                 result.push_back(ergodic.top()->val);
56                 root = ergodic.top()->right;
57                 ergodic.pop();
58             }
59         }
60         return result;
61     }
62 
63 };
64 
65 int main() {
66     Solution sol;
67     TreeNode* head2 = new TreeNode(2);
68     TreeNode* head3 = new TreeNode(3, nullptr, head2);
69     TreeNode* head1 = new TreeNode(1, head3, nullptr);
70     sol.recoverTree(head1);
71     vector<int> resultforeach = sol.inorderTraversal(head1);
72     for (int i = 0; i < resultforeach.size(); i++) {
73         cout << resultforeach[i] << " ";
74     }
75 
76 }