LeetCode 99. 恢复二叉搜索树
原题链接
困难
作者:
大明湖的鱼
,
2021-01-30 09:17:23
,
所有人可见
,
阅读 336
时间复杂度$O(n)$ 不考虑递归栈空间复杂度$O(1)$
还有一个Morris二叉树遍历算法可以用时间换空间,没仔细学,mark一下
代码
/**
* 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:
TreeNode* t1,*t2,*pre;
void recoverTree(TreeNode* root) {
inorder(root);
int tmp = t1->val;
t1->val = t2->val;
t2->val = tmp;
}
void inorder(TreeNode* root){
if(root == nullptr) return ;
inorder(root->left);
if(pre != nullptr && pre->val > root->val){
if(t1 == nullptr) t1 = pre;
t2 = root; //一定会找到两个节点,t1找到以后就非空了,只需更新t2就好。
//这样包含了一个逆序对的情况
}
pre = root;
inorder(root->right);
}
};