This is one of those problems where the clean idea matters more than the amount of code. For 99. Recover Binary Search Tree, the solution in this repository is mainly a two pointers solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, sliding window, greedy.
The notes already sitting in the source point us in the right direction:
- time: O(N), space: O(N)
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are inorder, inorder_revise, recoverTree, doWork.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(N), space: O(N)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 56 ms, faster than 20.38% of C++ online submissions for Recover Binary Search Tree.
02//Memory Usage: 55.2 MB, less than 5.06% of C++ online submissions for Recover Binary Search Tree.
03//time: O(N), space: O(N)
04/**
05 * Definition for a binary tree node.
06 * struct TreeNode {
07 * int val;
08 * TreeNode *left;
09 * TreeNode *right;
10 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
11 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
13 * };
14 */
15class Solution {
16public:
17 vector<TreeNode*> nodes;
18 vector<int> vals;
19
20 void inorder(TreeNode* node){
21 if(!node) return;
22 inorder(node->left);
23 nodes.push_back(node);
24 vals.push_back(node->val);
25 inorder(node->right);
26 }
27
28 void inorder_revise(TreeNode* node, int& order, vector<int>& indices_to_revise, vector<int>& vals_to_revise){
29 if(!node) return;
30 inorder_revise(node->left, order, indices_to_revise, vals_to_revise);
31 auto it = find(indices_to_revise.begin(), indices_to_revise.end(), order);
32 if(it != indices_to_revise.end()){
33 // cout << "revise " << node->val << " to " << vals_to_revise[it-indices_to_revise.begin()] << endl;
34 node->val = vals_to_revise[it-indices_to_revise.begin()];
35 }
36 ++order;
37 inorder_revise(node->right, order, indices_to_revise, vals_to_revise);
38 }
39
40 void recoverTree(TreeNode* root) {
41 inorder(root);
42
43 //the values in right order
44 sort(vals.begin(), vals.end());
45
46 vector<int> indices_to_revise;
47 vector<int> vals_to_revise;
48 for(int i = 0; i < nodes.size(); ++i){
49 //the node's value isn't the value it should be
50 if(nodes[i]->val != vals[i]){
51 indices_to_revise.push_back(i);
52 vals_to_revise.push_back(vals[i]);
53 }
54 }
55
56 int order = 0;
57 inorder_revise(root, order, indices_to_revise, vals_to_revise);
58 }
59};
60
61//Morris Traversal, threaded binary tree
62//https://leetcode.com/problems/recover-binary-search-tree/discuss/32559/Detail-Explain-about-How-Morris-Traversal-Finds-two-Incorrect-Pointer
63//Runtime: 48 ms, faster than 33.92% of C++ online submissions for Recover Binary Search Tree.
64//Memory Usage: 53.7 MB, less than 33.72% of C++ online submissions for Recover Binary Search Tree.
65//time: O(N), space: O(1)
66/**
67 * Definition for a binary tree node.
68 * struct TreeNode {
69 * int val;
70 * TreeNode *left;
71 * TreeNode *right;
72 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
73 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
74 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
75 * };
76 */
77class Solution {
78public:
79 TreeNode *cur, *prev;
80 TreeNode *first, *second;
81
82 void doWork(){
83 //do work related to this problem
84 if(prev != nullptr && prev->val > cur->val){
85 if(first == nullptr){
86 first = prev;
87 // cout << "first: " << prev->val << endl;
88 }
89 /*
90 also set second when first == nullptr,
91 this is so deal with the case that
92 first and second may be consecutive
93 */
94 second = cur;
95 // cout << "second: " << cur->val << endl;
96 }
97 //maintain the "prev" pointer
98 prev = cur;
99 };
100
101 void recoverTree(TreeNode* root) {
102 cur = root;
103 prev = nullptr;
104 first = second = nullptr;
105
106 //the framework is Morris traversal
107 while(cur){
108 if(cur->left){
109 //find its predecessor in its left subtree
110 TreeNode* pred = cur->left;
111 while(pred->right != nullptr && pred->right != cur){
112 pred = pred->right;
113 }
114
115 if(pred->right == nullptr){
116 /*
117 connect the predecessor's right to cur,
118 so we can come back to cur later
119 */
120 pred->right = cur;
121 /*
122 now that it is ensured that we can go back to cur later,
123 we can go to its left subtree safely
124 */
125 cur = cur->left;
126 }else{
127 //here pred->right == cur
128
129 doWork();
130 // cout << cur->val << endl;
131
132 pred->right = nullptr;
133 /*
134 we have visit cur's left subtree and cur itself,
135 so go to its right subtree
136 */
137 cur = cur->right;
138 }
139 }else{
140 doWork();
141 // cout << cur->val << endl;
142 cur = cur->right;
143 }
144 }
145
146 if(first != nullptr && second != nullptr){
147 swap(first->val, second->val);
148 }
149 }
150};Cost
Complexity
Time
O(N), space: O(N)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.