leetcode[99] Recover Binary Search Tree
題目：二叉樹中有兩個節點對換了值，恢復他們。
思路：
因為中序遍歷是有序的，如果中序遍歷後的數組出現亂序，說明就是交換的。從前往後，第一次亂序的第一個，後最後一次亂序的後一個，然後把這兩個值對換就好了。
想了個非常挫的辦法。
先中序遍歷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<int> &perm) // 中序遍歷得到數組
{
if (root == NULL) return ;
stack<TreeNode *> 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<TreeNode *> 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<int> 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<TreeNode *> sta;
vector<int> 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;
}
}
swap(sw1->val, sw2->val);
return ;
}
