第四天leetcode刷题

昨天因为在赶路所以刷题停更了一天，然后写了一下当时想到的一些事情，关于自己以后要去做什么，以及自己以后能去做什么。但是最后思考出来的结果并不是一个很确定的答案，而且还好是一个不确定的答案。任何事情最吸引我的地方就是它的未知性，如果一切都像剧透一样被告知了确定的答案，那样的人生会让我感到无力而又恐惧。
同时也明白其实刷题进厂真的是无数选择中的一种，我应该更加清醒的意识到自己每天在干什么，要去做什么。或许回老家，开一家烘焙店，或者回到大山里去，到海边的渔村里去，到国外的森林里去，或者去打两年工，告诉自己任何时候都有抛下一切的勇气，任何时候都可以放下现在的一切然后投入到另一种全新的生活中去，这样的前提都只能在单身的情况下完成。
说起来可笑曾经那么渴望拥有一段长久的感情，拥有之后反而会让我触碰到那种预知的边界。恰好她似乎也厌倦了装模做样的情侣问候，于是一拍即合两人分开。
但是我能够这样想清楚是因为我经历过那样的生活，以后的生活我还都没有经历过，我不知道还会产生怎样的想法，还会怎样成长。
那下面开始听歌：我不和你谈论-张悬

做题做题！！！
看题目：99.恢复二叉搜索树

题目中一个非常关键的要点：在二叉搜索树中，中序遍历得到的节点的值是单调递增的
所以在这道题目中要利用二叉搜索树的这个特性来判断交换的节点值。

这里有一个关于中序遍历的模板：

public void inorder(TreeNode root){
        if (root == null) return ;    //终止条件
        inorder(root.left);           //访问左子树
        对当前节点进行一些操作          //对根节点的相关操作
        inorder(root.right);          //访问右子树
    }

下面是通过代码：

class Solution {
public:  
    void traverse(TreeNode* root) {
        if (!root) return;
/*中序遍历*/
        traverse(root -> left);
        if (prev != nullptr) {
            if (root->val < prev->val) {
                if (a == nullptr) {
                    a = prev;
                } 
                b = root;
            }
        }
        prev = root;
/*中序遍历*/
        traverse(root -> right);
    }
    void recoverTree(TreeNode* root){
        traverse(root);
        swap(a -> val, b -> val);
    }
private:
    TreeNode *a = nullptr;
    TreeNode *b = nullptr;
    TreeNode *prev = nullptr;
};