LeetCode-99. Recover Binary Search Tree

LeetCode-99. Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2] 1 / 3 \ 2Output: [3,1,null,null,2] 3 / 1 \ 2

Example 2:

Input: [3,1,4,null,null,2] 3 / \1 4 / 2Output: [2,1,4,null,null,3] 2 / \1 4 / 3

Follow up:

A solution using O(n) space is pretty straight forward.Could you devise a constant space solution?

题解：

本人解法：

我觉得使用了引用空间复杂度也只是常量级。

可能有1-2个逆序对，如果只有一个逆序对就直接交换，如果有两个那么交换第一个逆序对第一个元素和第二个逆序对第二个元素即可。

class Solution {public: void findNodes(TreeNode* &root, TreeNode* &pre, TreeNode* &a, TreeNode* &b) { if (root == NULL) { return; } findNodes(root->left, pre, a, b); if (pre != NULL && pre->val >= root->val) { if (a == NULL) { a = pre; } b = root; } pre = root; findNodes(root->right, pre, a, b); } void recoverTree(TreeNode* root) { TreeNode *pre = NULL, *a = NULL, *b = NULL; findNodes(root, pre, a, b); swap(a->val, b->val); }};

参考别人代码，是使用Morris中序遍历二叉树：

morris遍历这里有一篇博客讲的非常详细

​

class Solution {public: void swap(int &a, int &b) { int idx = a; a = b; b = idx; } void recoverTree(TreeNode *root) { TreeNode *a = NULL, *b = NULL, *parent = NULL; TreeNode *cur = root, *pre = NULL; while (cur != NULL) { if (cur->left == NULL) { if (parent != NULL && parent->val > cur->val) { if (a == NULL) { a = parent; } b = cur; } parent = cur; cur = cur->right; } else { pre = cur->left; while (pre->right != NULL && pre->right != cur) { pre = pre->right; } if (pre->right == NULL) { pre->right = cur; cur = cur->left; } else { pre->right = NULL; if (parent->val > cur->val) { if (a == NULL) { a = parent; } b = cur; } parent = cur; cur = cur->right; } } } if (a != NULL && b != NULL) { swap(a->val, b->val); } }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。