?
题目：二叉树中有两个节点对换了值，恢复他们。
?
思路：
因为中序遍历是有序的，如果中序遍历后的数组出现乱序，说明就是交换的。从前往后，第一次乱序的第一个，后最后一次乱序的后一个，然后把这两个值对换就好了。
?
想了个非常挫的办法。
?
先中序遍历Binary Tree Inorder Traversal，然后在数组中找到两个值，然后再中序遍历找到那两个值，交换一下。虽然AC了，但不忍直视啊。
?
?
复制代码
/**
?* Definition for binary tree
?* struct TreeNode {
?* ? ? int val;
?* ? ? TreeNode *left;
?* ? ? TreeNode *right;
?* ? ? TreeNode(int x) : val(x), left(NULL), right(NULL) {}
?* };
?*/
class Solution {
public:
? ? void inorder(TreeNode *root, vector &perm) // 中序遍历得到数组
? ? {
? ? ? ? if (root == NULL) return ;
? ? ? ? stack sta;
? ? ? ??
? ? ? ? sta.push(root);
? ? ? ? TreeNode *p = root -> left, *cen;
? ? ? ??
? ? ? ? while(!sta.empty())
? ? ? ? {
? ? ? ? ? ? if (p)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? sta.push(p);
? ? ? ? ? ? ? ? p = p -> left;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? cen = sta.top();
? ? ? ? ? ? ? ? sta.pop();
? ? ? ? ? ? ? ? perm.push_back(cen -> val);
? ? ? ? ? ? ? ? if (cen -> right)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? sta.push(cen -> right);
? ? ? ? ? ? ? ? ? ? p = cen -> right -> left;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? ? ? void inorderC(TreeNode *root,int val1, int val2) // 中序遍历将对应值修改
? ? {
? ? ? ? if (root == NULL) return ;
? ? ? ? stack sta;
? ? ? ??
? ? ? ? sta.push(root);
? ? ? ? TreeNode *p = root -> left, *cen;
? ? ? ??
? ? ? ? while(!sta.empty())
? ? ? ? {
? ? ? ? ? ? if (p)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? sta.push(p);
? ? ? ? ? ? ? ? p = p -> left;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? cen = sta.top();
? ? ? ? ? ? ? ? sta.pop();
? ? ? ? ? ? ? ? if(cen -> val == val1)
? ? ? ? ? ? ? ? ? ? cen -> val = val2;
? ? ? ? ? ? ? ? else if(cen -> val == val2)
? ? ? ? ? ? ? ? ? ? cen -> val = val1;
? ? ? ? ? ? ? ? if (cen -> right)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? sta.push(cen -> right);
? ? ? ? ? ? ? ? ? ? p = cen -> right -> left;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? void recoverTree(TreeNode *root)?
? ? {
? ? ? ? if (!root) return ;
? ? ? ? vector perm;
? ? ? ? inorder(root, perm);
? ? ? ? int val1, val2;
? ? ? ? bool flag = true;
? ? ? ? for (int i = 0; i < perm.size(); ++i)
? ? ? ? {
? ? ? ? ? ? if (flag && i + 1 < perm.size() && perm[i] > perm[i+1]) // 第一次比后一个大的数
? ? ? ? ? ? {
? ? ? ? ? ? ? ? val1 = perm[i];
? ? ? ? ? ? ? ? flag = false;
? ? ? ? ? ? }
? ? ? ? ? ? if (i - 1 >= 0 && perm[i] < perm[i-1]) // 最后一个比前面小的数
? ? ? ? ? ? ? ? val2 = perm[i];
? ? ? ? }
? ? ? ? inorderC(root, val1, val2);
? ? }
};
复制代码
然后就想到改进，在一次中序遍历中就记录两个节点，然后交换值。
?
经过优化之后果然好看多了。
?
复制代码
/**
?* Definition for binary tree
?* struct TreeNode {
?* ? ? int val;
?* ? ? TreeNode *left;
?* ? ? TreeNode *right;
?* ? ? TreeNode(int x) : val(x), left(NULL), right(NULL) {}
?* };
?*/
class Solution {
public:
? ? void recoverTree(TreeNode *root)?
? ? {
? ? ? ? if (!root) return ;
? ? ? ? stack sta;
? ? ? ? vector perm;
? ? ? ? TreeNode *p = root, *sw1, *sw2, *pre = NULL;
? ? ? ? bool flag1 = false; // 分别表示sw1是否找到
? ? ? ? while(p || !sta.empty())
? ? ? ? {
? ? ? ? ? ? while(p)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? sta.push(p);
? ? ? ? ? ? ? ? p = p -> left;
? ? ? ? ? ? }
? ? ? ? ? ? if (!sta.empty())
? ? ? ? ? ? {
? ? ? ? ? ? ? ? p = sta.top();
? ? ? ? ? ? ? ? // 在//这之间和pre比较?
? ? ? ? ? ? ? ? if (pre && !flag1 && pre -> val > p -> val)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? sw1 = pre; flag1 = true; ? // sw1是第一次违法的第一个数
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (pre && pre -> val > p -> val)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? sw2 = p; // sw2是最后一次违法的第二个数
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? //
? ? ? ? ? ? ? ? sta.pop();
? ? ? ? ? ? ? ? pre = p; // 每次加入的对应pre；下一次要加入的时候那么pre就是之前一个了
? ? ? ? ? ? ? ? perm.push_back(p -> val);
? ? ? ? ? ? ? ? p = p -> right;
? ? ? ? ? ? }
? ? ? ? }
?