欢迎访问LeetCode题解合集
题目描述
给你二叉搜索树的根节点 root
,该树中的两个节点被错误地交换。请在不改变其结构的情况下,恢复这棵树。
进阶:使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗?
示例 1:
[HTML_REMOVED]
[HTML_REMOVED]
输入:root = [1,3,null,null,2]
输出:[3,1,null,null,2]
解释:3 不能是 1 左孩子,因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2:
[HTML_REMOVED]
[HTML_REMOVED]
输入:root = [3,1,4,null,null,2]
输出:[2,1,4,null,null,3]
解释:2 不能在 3 的右子树中,因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
提示:
- 树上节点的数目在范围
[2, 1000]
内 - $-2^{31} \le Node.val \le 2^{31} - 1$
题解:
二叉搜索树的中序遍历是递增序列,根据这个特性来做。
因为交换了两个节点,所以递增序列中一定会出现 $a_i > a_{i+1}$ 的情况。
假设递增序列为 [1, 2, 3, 4, 5, 6, 7]
,如果交换两个不相邻的数字,比如 2
和 6
,那么序列变成 [1, 6, 3, 4, 5, 2, 7]
,序列中有两个位置不满足;
如果交换 2
和 3
,那么结果中就只有一个位置不满足。于是,可以找到这样的位置,将它们交换。
需要注意的是,如果有两个位置不满足,假设 $a_i > a_{i+1}$ 和 $a_j > a_{j+1}$,那么交换位置是 $a_i$ 和 $a_{j+1}$。
法一:
显示中序遍历,将中序遍历结果保存到数组中,遍历数组找到这些位置。
时间复杂度:$O(n)$
额外空间复杂度:$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<TreeNode*> inoder;
void dfs( TreeNode* root ) {
if ( root ) {
dfs( root->left );
inoder.emplace_back( root );
dfs( root->right );
}
}
void recoverTree(TreeNode* root) {
TreeNode *first = nullptr, *second = nullptr;
dfs( root );
int n = inoder.size();
for ( int i = 0; i < n - 1; ++i ) {
if ( inoder[i]->val > inoder[i + 1]->val ) {
second = inoder[i + 1];
if ( !first ) first = inoder[i];
else break;
}
}
swap( first->val, second->val );
}
};
/*
时间:36ms,击败:91.18%
内存:56.7MB,击败:79.94%
*/
法二:
因为我们只关心中序遍历序列中 相邻位置的大小关系是否满足条件 ,且最多两个位置不满足,所以我们只需要维护当前中序遍历序列中的最后一个节点,与下一个节点进行判断即可。
时间复杂度:$O(n)$
额外空间复杂度:$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void dfs( TreeNode* root, TreeNode*& pre, TreeNode*& first, TreeNode*& second ) {
if ( root ) {
dfs( root->left, pre, first, second );
if ( pre && pre->val >= root->val ) {
second = root;
if ( !first ) first = pre;
else return;
}
pre = root;
dfs( root->right, pre, first, second );
}
}
void recoverTree(TreeNode* root) {
TreeNode *pre = nullptr, *first = nullptr, *second = nullptr;
dfs( root, pre, first, second );
swap( first->val, second->val);
}
};
/*
时间:28ms,击败:97.82%
内存:56.1MB,击败:98.88%
*/
迭代模拟递归版本:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void recoverTree(TreeNode* root) {
stack<TreeNode*> stk;
TreeNode *pre = nullptr, *first = nullptr, *second = nullptr;
while ( stk.size() || root ) {
while ( root ) {
stk.push( root );
root = root->left;
}
root = stk.top();
stk.pop();
if ( pre && pre->val >= root->val ) {
second = root;
if ( !first ) first = pre;
else break;
}
pre = root;
root = root->right;
}
swap( first->val, second->val );
}
};
/*
时间:28ms,击败:97.82%
内存:57.8MB,击败:23.48%
*/
法三:
上述两种方法都需要 $O(n)$ 的额外空间复杂度,而这题要求 常数 的空间复杂度,所以是时候上 Morris遍历 了。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode *pre = nullptr, *first = nullptr, *second = nullptr;
TreeNode *mostright = nullptr;
while ( root ) {
mostright = root->left;
if ( mostright ) {
while ( mostright->right && mostright->right != root )
mostright = mostright->right;
if ( !mostright->right ) {
mostright->right = root;
root = root->left;
continue;
} else mostright->right = nullptr;
}
if ( pre && pre->val >= root->val ) {
second = root;
if ( !first ) first = pre;
}
pre = root;
root = root->right;
}
swap( first->val, second->val );
}
};
/*
时间:36ms,击败:91.18%
内存:56.1MB,击败:99.59%
*/