Leetcode 99. Recover Binary Search Tree O(1)

本文主要是介绍Leetcode 99. Recover Binary Search Tree O(1)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目中要求用constant space去结题，那就不能使用中序遍历类似的递归写法，因为这些的空间复杂度平均水平是$O(logN)$。那么只有使用一种（新的）遍历算法Morris Traversal。

然后结合中序遍历的结题思路，左子树的最大值要小于根节点和右子树的值。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:void recoverTree(TreeNode* root) {TreeNode* cur = root,* pre = nullptr;while(cur){if(cur->left == nullptr){iserror(cur);last = cur;//printf("%d\n", last->val);cur = cur->right;}else{pre = cur->left;while(pre->right != nullptr && pre->right != cur)pre = pre->right;if(pre->right == nullptr){pre->right = cur;cur = cur->left;}else{pre->right = nullptr;iserror(cur);last = cur;//printf("%d\n", last->val);cur = cur->right;}}}swap(node1->val, node2->val);}
private:TreeNode* node1 = nullptr;TreeNode* node2 = nullptr;TreeNode* last = new TreeNode(INT_MIN);void iserror(TreeNode* cur){//printf("%d %d\n", last->val, cur->val);if(!node1 && last->val > cur->val)   node1 = last;if( node1 && last->val > cur->val)   node2 = cur;}
};

这篇关于Leetcode 99. Recover Binary Search Tree O(1)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---