scoyer_result(C++)


  • 0
    H

    An important property of binary index tree is that you can get the sorted sequence by inorder traverse.So we can get a fake sorted sequence which swaps two elements by mistake.Now the question is that giving a sequence which you can swap two elements for getting a sorted sequence, restore it.It's easy to solve this problem.You just need to scan it from begin to end get the first wrong element, and scan it from end to begin to get second element.After getting a sorted element,dfs again to assign it to the tree.

    First version:

    class Solution {
    public:
      void recoverTree(TreeNode* root) {
        if (root == NULL) return;
        vector<int> vec_val;
        dfs(root, vec_val, Before);
        repair(vec_val);
        dfs(root, vec_val, After);
      }
    private:
      enum op_type { Before, After };
      void dfs(TreeNode* root, vector<int>& vec, op_type op) {
        if (root->left) dfs(root->left, vec, op);
        if (op == Before) {
          vec.push_back(root->val);
        }
        else {
          root->val = vec.back();
          vec.pop_back();
        }
        if (root->right) dfs(root->right, vec, op);
      }
      void repair(vector<int>& vec) {
        int n = vec.size();
        int id1, id2;
        for (int i = 0; i < n - 1; i++) if (vec[i] > vec[i + 1]) {
          id1 = i; break;
        }
        for (int i = n - 1; i > 0; i--) if (vec[i] < vec[i - 1]) {
          id2 = i; break;
        }
        swap(vec[id1], vec[id2]);
        reverse(vec.begin(), vec.end());
      }
    };
    

    After I refer to the discussion,I find a easier way to code.The thinking is similar,but you just only traverse tree once.Define two pointers one and two for pointing two wrong elements.The first time scan the wrong element it's one, the last time scan the wrong element is two.Think about why(refer to my solution of first version)

    Second version:

    class Solution {
    public:
      Solution() : one(NULL), two(NULL), pre(NULL) {}
      void recoverTree(TreeNode* root) {
        dfs(root);
        swap(one->val, two->val);
      }
    private:
      TreeNode* one;
      TreeNode* two;
      TreeNode* pre;
      void dfs(TreeNode* root) {
        if (root->left) dfs(root->left);
        if (pre && pre->val > root->val) {
          if (one == NULL) one = pre;
          two = root;
        }
        pre = root;
        if (root->right) dfs(root->right);
      }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.