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); }
};