[Leetcode] Recover binary search tree 恢复二叉搜索树

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

Recover the tree without changing its structure.

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

confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".

最简单的办法应该是，中序遍历二叉树，将各个结点的值存储在一维向量中，然后进行一次赋值操作。这种方法对任意个数的节点错乱都实用。

详情见Grangyang的博客

 /**

  * Definition for binary tree

  * struct TreeNode {

  *     int val;

  *     TreeNode *left;

  *     TreeNode *right;

  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

  * };

  */

 class Solution {

 public:

     void recoverTree(TreeNode *root)

     {

         vector<TreeNode *> treeNode;

         vector<int> nodeVal;

         inoder(root,treeNode,nodeVal);

         sort(nodeVal.begin(),nodeVal.end());

         for(int i=;i<treeNode.size();++i)

             treeNode[i]->val=nodeVal[i];

     }

     void inoder(TreeNode *root,vector<TreeNode *> &treeNode,vector<int> &nodeVal)

     {

         if(root==NULL)  return;

         inoder(root->left,treeNode,nodeVal);

         treeNode.push_back(root);

         nodeVal.push_back(root->val);

         inoder(root->right,treeNode,nodeVal);

     }

 };

方法二：

用三个指针，w1,w2分别指向第一、二个错误的地方。pre指向当前结点中序遍历中的前一个结点。因有两个结点交换了，所以二叉树的中序遍历中会出现违背有序的情况，一、即中序遍历中相邻的结点被交换，则违背有序的情况出现一次，如132456；二、中序遍历中不相邻的两个结点的值被交换，则出现两次违背有序情况，如153426.针对情况1，pre=3，w1=pre即为3，w2=root，即为2，在后续的遍历中没有违背有序的情况，所以交换w1和w2即可；针对情况2，找到第一个错误点后，w1 ！=NULL了，所以，第二个错误点w2=root，第一逆序的前结点，第二逆序的后结点，交换两者即可。

 /**

  * Definition for binary tree

  * struct TreeNode {

  *     int val;

  *     TreeNode *left;

  *     TreeNode *right;

  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

  * };

  */

 class Solution {

 public:

     TreeNode *w1,*w2,*pre;

     void recoverTree(TreeNode *root)

     {

         if(root==NULL)  return;

         w1=w2=pre=NULL;

         find(root);

         swap(w1->val,w2->val);

     }

     void find(TreeNode *root)

     {

         if(root==NULL)  return;

         find(root->left);

         if(pre&&pre->val > root->val)

         {

             if(w1==NULL)    //情况1

             {

                 w1=pre;

                 w2=root;

             }

             else            //情况2

                 w2=root;

         }

         pre=root;

         find(root->right);

     }

 };

方法三

层次遍历中的Mirror方法，修改部分得到。真正的O(1)。

// Now O(1) space complexity

class Solution {

public:

    void recoverTree(TreeNode *root) {

        TreeNode *first = NULL, *second = NULL, *parent = NULL;

        TreeNode *cur, *pre;

        cur = root;

        while (cur) {

            if (!cur->left) {

                if (parent && parent->val > cur->val) {

                    if (!first) first = parent;

                    second = cur;

                }

                parent = cur;

                cur = cur->right;

            } else {

                pre = cur->left;

                while (pre->right && pre->right != cur) pre = pre->right;

                if (!pre->right) {

                    pre->right = cur;

                    cur = cur->left;

                } else {

                    pre->right = NULL;

                    if (parent->val > cur->val) {

                        if (!first) first = parent;

                        second = cur;

                    }

                    parent = cur;

                    cur = cur->right;

                }

            }

        }

        if (first && second) swap(first->val, second->val);

    }

};

巴特西

[Leetcode] Recover binary search tree 恢复二叉搜索树

最新文章

热门文章