LC99.恢复二叉搜索树

image.png

思路：

  • 分成三步走：1. 把二叉排序树倒进一个数组当中 2.在数组内部找到两个数字分别的位置 3.搜索二叉排序树，交换指定位置的数值
  • 把二叉树倒进数组中：中序遍历即可
  • 双指针去找各自的位置，也不难

  • 递归查找，遇到指定的数值就进行交换

    代码：

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. public:
    14.   // 倒进数组里面
    15.   void dfs(TreeNode* root, vector<int>& nums) {
    16.       if (!root) {
    17.           return;
    18.       }
    20.       if (root->left) {
    21.           dfs(root->left, nums);
    22.       } 
    23.       nums.push_back(root->val);
    24.       if (root->right) {
    25.           dfs(root->right, nums);
    26.       }
    27.   }
    29.   // 查找对应位置
    30.   pair<int, int> findPos(vector<int>& nums) {
    31.       int lp = 0, rp = 0;
    32.       int n = nums.size();
    33.       pair<int, int> pos;
    34.       int cnt = 0;
    35.       for (int i = 0; i < n - 1; ++i) {
    36.           if (nums[i] > nums[i + 1]) {
    37.               pos.first = nums[i];
    38.               break;
    39.           }
    40.       }
    42.       for (int i = n - 1; i > 0; --i) {
    43.           if (nums[i] < nums[i - 1]) {
    44.               pos.second = nums[i];
    45.               break;
    46.           }
    47.       }
    48.       return pos;
    49.   }
    51.   // 交换位置
    52.   void exchange(TreeNode* root, int x, int y, int cnt) {
    53.       if (!root) {
    54.           return;
    55.       }
    57.       if (root->val == x && cnt <= 1) {
    58.           root->val = y;
    59.           cnt += 1;
    60.       } else if (root->val == y && cnt <= 1) {
    61.           root->val = x;
    62.           cnt += 1;
    63.       }
    65.       if (root->left) exchange(root->left, x, y, cnt);
    66.       if (root->right) exchange(root->right, x, y, cnt);
    67.   }
    69.   void recoverTree(TreeNode* root) {
    70.       // 三步走：1.倒进一个数组当中 2.找到节点对应数值 3，进行交换
    71.       vector<int> nums;
    72.       dfs(root, nums);
    74.       // for (int i = 0, n = nums.size(); i < n; ++i) {
    75.       //     cout << nums[i] << " ";
    76.       // }
    77.       // cout << endl;
    78.       pair<int, int> pos = findPos(nums);
    79.       // cout << pos.first << " " << pos.second << endl;
    80.       exchange(root, pos.first, pos.second, 0);
    81.   }
    82. };