[数据结构与算法]LeetCode 99. 恢复二叉搜索树 -- 中序遍历+排序

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

示例 1：

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

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

提示：

树上节点的数目在范围 [2, 1000] 内
-231 <= Node.val <= 231 - 1

题解

排个序中序遍历下就行了。

AC代码

/**
 * 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) {}
 * };
 */
class Solution {
public:
    vector<int>q;
    void dfs(TreeNode* root)
    {
        if(root==NULL)return;
        q.push_back(root->val);
        dfs(root->left);
        dfs(root->right);
    }
    int node_id;
    void dfs2(TreeNode* root)//中序遍历
    {
        if(root==NULL)return ;
        dfs2(root->left);
        root->val = q[node_id];
        node_id ++;
        dfs2(root->right);
    }
    void recoverTree(TreeNode* root) 
    {
        dfs(root);
        sort(q.begin(),q.end());
        node_id = 0;
        dfs2(root);
    }
};