算法设计与分析2018.9第一周作业

题目：99. Recover Binary Search Tree
链接：https://leetcode.com/problems/recover-binary-search-tree/description/
Difficulty:Hard

在写之前先补充一些c++的基本语法
看构造函数发现有find_if这个函数，

void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

根据网上用法
find_if：根据指定的pred运算条件（以仿函数表示），循环查找[first,last)内的所有元素，找出第一个令pred运算结果true者。如果找到就返回一个InputIterator指向该元素，否则就返回迭代器last。

template<class InputIterator,class Predicate>  
InputIterator find_if(InputIterator first,InputIterator last,Predicate pred)

其中的Predicate pred除了可以用上面的匿名函数来代替，也可以用函数对象替代
其中函数对象的使用方法如下：

class StudentAdapter:public unary_function<Student,bool>
//传入student一个参数,也可以用binary( , , bool)传入两个参数
{
private:
    string name;
public:
    explicit StudentAdapter(string iname):name(iname){}
    bool operator()(const Student& student)//重载运算符
    {
        return (student.name==name);
    }
};
main主函数中：
find_if(admin.begin(),admin.end(),StudentAdapter("lanzhihui"));

本题目的是找出BST中的两个放错位置的节点
主要的方法是利用中序遍历，找出两个没有从小到大放的数，例如某二叉树中序遍历之后为1,3,2,4那么就是3和2是需要交换的节点。
下面是通过的代码：

class Solution {
public:
  vector<TreeNode*> trees;
    TreeNode* FirstNode=NULL;
    TreeNode* SecondNode=NULL;

    void inorder(TreeNode* root) {
        if (root == NULL) {
            return;
        }
        inorder(root->left);
        trees.push_back(root);
        inorder(root->right);
    }
    void swap(TreeNode& FirstNode,TreeNode& SecondNode) {
        int temp;
        temp = FirstNode.val;
        FirstNode.val=SecondNode.val;
        SecondNode.val = temp;
    }
    void recoverTree(TreeNode* root) {
        inorder(root);
        for (int i = 0; i < trees.size()-1; i++) {
            if (trees[i]->val > trees[i + 1]->val) {
                FirstNode=trees[i];
                break;
            }
        }
        for (int i = trees.size() - 1; i >0; i--) {
            if (trees[i]->val < trees[i - 1]->val) {
                SecondNode = trees[i];
                break;
            }
        }
        //cout << "before swap:" << FirstNode->val << " " << SecondNode->val << endl;
        swap(*FirstNode, *SecondNode);
        //cout<<"after swap:"<< FirstNode->val << " " << SecondNode->val << endl;
    }
};