LeetCode99 恢复二叉搜索树

链接: https://leetcode-cn.com/problems/recover-binary-search-tree

题意

给定一个二叉查找树,已知有两个节点被不小心交换了,试复原此树。

解法

利用二叉查找树的中序遍历有序性
找到不符合条件的节点进行交换
每次记录prev节点
这里一开始写的时候陷入了一个困境
即如何记录prev节点 想的时候想错了
误把遍历时候访问的节点当成了prev节点
最后使用全局变量的方式 每次中序遍历访问的节点

出现顺序不符的情况有两种,一种是遍历整个过程出现一次次序错误,还有一种是两次次序错误
如果一次,则说明这两个节点需要交换
如果两次,则交换这两个节点
要注意交换的这两个节点分别是第一个的prev和第二个root(这里一开始也卡住了)
细节见代码

代码

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
class Solution {
public:
vector<TreeNode*> vt;
TreeNode* prev;
void inOrder(TreeNode* root) {
if(!root) return;
inOrder(root -> left);
if(prev) {
if (prev -> val > root -> val) {
if (vt.empty()) {
vt.push_back(prev);
vt.push_back(root);
}
else {
vt.pop_back();
vt.push_back(root);
}
}
}
prev = root;
inOrder(root -> right);
}
void recoverTree(TreeNode* root) {
inOrder(root);
int val = vt[0] -> val;
vt[0] -> val = vt[1] -> val;
vt[1] -> val = val;
}
};