[toc]
# 牵扯到的题
leetcode 94
leetcode 99
LeetCode 144
LeetCode 145
# 原题
给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。 进阶：使用 O (n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
# 题解
这道题用 O (n) 的存储空间很好解决，即中序遍历记录所有的值，然后找到其中逆序的两个值就可以了 但题目中说的是常数空间，这就产生了一个问题
常数空间解
首先，我们对树进行中序遍历，因为是二叉搜索树，所以一定是升序的.
所以，如果在遍历的过程中出现了逆序的数，自然就是错位的那两个中的一个，这样找到两个交换位置即可 注意：第一个逆序数一定是比后面大，
第二个逆序数一定是比前面小 但是常数空间不能用递归，所以就需要用到迭代进行中序遍历的方式
# 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
class Solution {
public:
void recoverTree(TreeNode* root) {
bool first= true;
TreeNode* s1=nullptr;
TreeNode* s2=nullptr;
TreeNode* preNode=nullptr;
stack<TreeNode*> st;
if(root){
while(root !st.empty()){
if(root){
st.push(root);
root = root->left;
}else{
root = st.top();
st.pop();
if(preNode!=nullptr){
if(preNode->val > root->val){
s2=root;
if(s1==nullptr) s1 = preNode;
else break;
}
}
preNode = root;
root = root->right;
}
}
}
swap(s1->val,s2->val);
}
};
|
# leetcode 94 中序遍历的迭代实现
# 思路
建立一个 stack, 手动模拟递归
- 每次往栈中 push 左节点，直到左节点为空
- 然后从栈顶弹出一个元素，这个元素放到答案列表中
- 在尝试将该元素的右节点放入栈中
# 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
if(root){
while(root !st.empty()){
if(root){
st.push(root);
root = root->left;
}else{
root = st.top();
st.pop();
ans.push_back(root->val);
root = root->right;
}
}
}
return ans;
}
};
|
# Leetcode 144 迭代实现先序遍历
# 思路
先序遍历是 根左右 模拟的时候，因为栈是先进后出，所以需要先把右节点推入，后推入左节点，保证每次迭代最后入栈的是左节点。然后每次把第一个记录一下就可以了
# 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
TreeNode* cur;
if(root){
st.push(root);
cur = root;
while(!st.empty()){
cur = st.top();
st.pop();
if(cur){
ans.push_back(cur->val);
if(cur->right){
st.push(cur->right);
}
if(cur->left){
st.push(cur->left);
}
}
}
}
return ans;
}
};
|
