交换二叉搜索树的两个节点,要求复原。
不确定我的做法对不对,我只是在value的程度上把他们复原了。但是原文说不要破坏他们的结构?
想法很简单中序遍历+线性数组纠正
class Solution { public: void recoverTree(TreeNode *root) { if(root == NULL)return ; treeArray.clear(); inOrder(root); int x,y; int flag = 0; for(int i = 0;i < treeArray.size();i++) { if(i == 0 && treeArray[i] > treeArray[i+1] && i < treeArray.size()-1) { if(flag == 0) { x = i; flag = 1; } else { y = i; } continue; } if(i == treeArray.size()-1 && treeArray[i] < treeArray[i-1] && i > 0) { if(flag == 0) { x = i; flag = 1; } else { y = i; } continue; } if( i > 0 && i < treeArray.size()-1 && treeArray[i] > treeArray[i-1] && treeArray[i] > treeArray[i+1]) { if(flag == 0) { x = i; flag = 1; } else { y = i; } continue; } if( i > 0 && i < treeArray.size()-1 && treeArray[i] < treeArray[i-1] && treeArray[i] < treeArray[i+1] ) { if(flag == 0) { x = i; flag = 1; } else { y = i; } continue; } } if(flag == 0) { for(int i = 0;i < treeArray.size()-1;i++) { if(treeArray[i] > treeArray[i+1]) { x = i; y = i+1; break; } } } queryTree(root,x,y); } private: vector<int>treeArray; void inOrder(TreeNode * root) { if(root->left != NULL) inOrder(root->left); treeArray.push_back(root->val); if(root->right != NULL) inOrder(root->right); } void queryTree(TreeNode * root,int x,int y) { if(root->val == treeArray[x]) { root->val = treeArray[y]; } else if (root->val == treeArray[y]){ root->val = treeArray[x]; } if(root->left != NULL) queryTree(root->left,x,y); if(root->right != NULL) queryTree(root->right,x,y);<br /> } };