leetcode 99. 恢复二叉搜索树

1.题目要求:


2.解题步骤:

采用两次中序遍历，第一次是采用中序遍历把结点的值赋给数组，第二次是把排序后的数组反赋给树中的结点

3.解题代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //先用一次中序遍历把结点的元素放入数组中
    void inorder_travel(TreeNode* root,vector<int>& nums){
        if(root == NULL){
            return;
        }
        inorder_travel(root->left,nums);
        nums.push_back(root->val);
        inorder_travel(root->right,nums);
    }
    //进行依次排序后再把数组的元素重新赋给结点中
    void inorder_travel_assign(TreeNode* root,vector<int>& nums,int& index){
        if(root == NULL){
            return;
        }
        inorder_travel_assign(root->left,nums,index);
        root->val = nums[index];
        index++;
        inorder_travel_assign(root->right,nums,index);
    }
    void recoverTree(TreeNode* root) {
        vector<int> array;
        //第一次中序遍历
        inorder_travel(root,array);
        //给数组元素排序
        sort(array.begin(),array.end());
        int i  = 0;
        //第二次中序遍历
        inorder_travel_assign(root,array,i); 
    }
};