99恢复二叉搜索树（让两个值交换位置）

这个题我主要学到的方法是怎么将两个不是紧临的数字交换位置首先二叉树中两个数字位置颠倒必然会产生逆序如1 2 3 4 5 6 71 2 7 4 5 6 3如上7 4与6 3 是两处逆序的地方我们只需要定义一个x定义一个y,一个记录逆序后的节点一个记录逆序前的节点。然后再交换两者位置即可/** * 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 { vectorTreeNode* ret; void inorder(TreeNode* root){ if(rootNULL){ return ; } else{ inorder(root-left); ret.push_back(root); inorder(root-right); } } void way(TreeNode* root){ TreeNode* xNULL; TreeNode* yNULL; for(int i0;iret.size()-1;i){ if(ret[i]-valret[i1]-val){ //记录每次逆序的后一个节点 yret[i1]; if(xNULL){ //记录每次逆序的前一个节点 xret[i]; } } } if(x!NULLy!NULL){ int tmpx-val; x-valy-val; y-valtmp; } } public: void recoverTree(TreeNode* root) { ret.clear(); inorder(root); TreeNode* xNULL; TreeNode* yNULL; /*for(int i0;iret.size()-1;i){ if(ret[i]-valret[i1]-val){ //记录每次逆序的后一个节点 yret[i1]; if(xNULL){ //记录每次逆序的前一个节点 xret[i]; } } } if(x!NULLy!NULL){ int tmpx-val; x-valy-val; y-valtmp; } */ way(root); } };