LeetCode:恢复二叉搜索树
前几天写的题了,虽然空间复杂度满足了题目进阶要求,但是感觉效率低还是有改进的空间,先放在这里以后有空了来改。
题目简介:
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下,恢复这棵树。
示例 1:
输入: [1,3,null,null,2]
1
/
3
\
2
输出: [3,1,null,null,2]
3
/
1
\
2
示例 2:
输入: [3,1,4,null,null,2]
3
/ \
1 4
/
2
输出: [2,1,4,null,null,3]
2
/ \
1 4
/
3
进阶:
使用 O(n) 空间复杂度的解法很容易实现。
你能想出一个只使用常数空间的解决方案吗?
题解:
我个人的思路是穷举所有根到叶子节点,找出不平衡的子树,然后交换值,再进行穷举检查,空间复杂度的话,应该是只用到O(n),因为只存储根(包含子树的根)结点。
class Solution {
public:
void recoverTree(TreeNode* root) {
stack<TreeNode*>_stk;
_stk.push(root);
while(!_stk.empty()){
auto cur=_stk.top();
auto l=left(cur,cur->left);
if(!l)
continue;
auto r=right(cur,cur->right);
if(!r)
continue;
_stk.pop();
if(cur->left!=NULL)
_stk.push(cur->left);
if(cur->right!=NULL)
_stk.push(cur->right);
}
}
bool left(TreeNode* root,TreeNode *next){
if(next==NULL)
return true;
if(root->val>next->val){
auto l=left(root,next->left);
if(!l)
return false;
auto r=left(root,next->right);
if(!r)
return false;
return true;
}
else{
swap(root->val,next->val);
return false;
}
}
bool right(TreeNode* root,TreeNode *next){
if(next==NULL)
return true;
if(root->val<next->val){
auto l=right(root,next->left);
if(!l)
return false;;
auto r=right(root,next->right);
if(!r)
return false;
return true;
}
else{
swap(root->val,next->val);
return false;
}
}
};