LeetCode_99_恢复二叉搜索树

题目描述：

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

示例：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：
1. 树上节点的数目在范围 [2, 1000] 内
2. -2^31 <= Node.val <= 2^31 - 1

解法1：中序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

//二叉查找树(Binary Search Tree,BST)是一种特殊的二叉树：对于每个父节点，其左子节点的值小于等于父节点的值，其右子节点的值大于等于父节点的值
//因此对于一个二叉查找树，我们可以在O(nlogn)的时间内查找一个值是否存在：从根节点开始，若当前节点的值大于查找值则向左下走，若当前节点的值小于查找值则向右下走
//因为二叉查找树是有序的，对其中序遍历的结果即为排好序的数组
class Solution {
public:

    TreeNode* t1 = nullptr, *t2 = nullptr, *pre = nullptr;

    void recoverTree(TreeNode* root) {

        inorder(root);

        //交换t1、t2节点的值
        int temp = t1->val;
        t1->val = t2->val;
        t2->val = temp;
    }

    void inorder(TreeNode* root) {

        if (root == nullptr) return;

        //先中序遍历这个二叉查找树，同时设置一个pre指针，记录当前节点中序遍历时的前节点
        //如果当前节点小于pre节点的值，说明需要调整次序
        inorder(root->left);

        if (pre != nullptr && pre->val > root->val) {

            if (t1 == nullptr) {

                t1 = pre;
            }
            
            t2 = root;
        }
        pre = root;

        inorder(root->right);
    }

};