LeetCode99 Recover Binary Search Tree

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

Recover the tree without changing its structure. （Hard）

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

分析：

BST的中序遍历应该是递增的，我们考虑这样一个中序遍历序列1,2,6,4,5,3,7，其中3,6是交换了位置的。

所以我们就按照中序遍历的顺序遍历树，记录cur, prev, beforePrev三个变量；

第一次出现before < prev > cur的prev即为要交换的第一个元素，最后一个满足beforePrev > prev < cur的即为要交换的另一个元素。

然后再遍历一遍把这两个节点找出来，交换其value值即可。

注意：比如1,0这种样例，当最后一个节点是被交换的元素的时候，无法用上述判断，但如果其满足prev > cur说明cur即为要交换的元素。

代码：

 /**

  * 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 {

     int beforePrev = -0x7FFFFFFF, prev = -0x7FFFFFFF, cur = -0x7FFFFFFF;

     int s1 = -0x7FFFFFFF, s2 = -0x7FFFFFFF;

     TreeNode* t1;

     TreeNode* t2;

 private:

     void helper(TreeNode* root) {

         if (root == nullptr) {

             return;

         }

         helper(root -> left);

         beforePrev = prev;

         prev = cur;

         cur = root -> val;

         if (beforePrev < prev && prev > cur && s1 == -0x7FFFFFFF) {

             s1 = prev;

         }

         if (beforePrev > prev && prev < cur ) {

             s2 = prev;

         }

         helper(root -> right);

     }

     void dfs(TreeNode* root) {

         if (root == nullptr) {

             return;

         }

         dfs(root -> left);

         if (root -> val == s1) {

             t1 = root;

         }

         if (root -> val == s2) {

             t2 = root;

         }

         dfs(root -> right);

     }

 public:

     void recoverTree(TreeNode* root) {

         helper(root);

         if (cur < prev) {

             s2 = cur;

         }

         dfs(root);

         swap(t1 -> val, t2 -> val);

         return;

     }

 };

巴特西

LeetCode99 Recover Binary Search Tree

最新文章

热门文章