LeetCode 99. Restore binary search tree -- medium order traversal + sorting

99. Restore binary search tree
    Give you the root node of the binary search tree root , In the tree just The values of the two nodes are incorrectly exchanged . Please... Without changing its structure , Restore the tree .

Example 1：

Input ：root = [1,3,null,null,2]
Output ：[3,1,null,null,2]
explain ：3 It can't be 1 The left child , because 3 > 1 . In exchange for 1 and 3 Make the binary search tree efficient .
Example 2：

Input ：root = [3,1,4,null,null,2]
Output ：[2,1,4,null,null,3]
explain ：2 Can't be in 3 In the right subtree , because 2 < 3 . In exchange for 2 and 3 Make the binary search tree efficient .

Tips ：

The number of nodes on the tree is in the range [2, 1000] Inside
-231 <= Node.val <= 231 - 1

Answer key

Arrange an order and traverse the middle order .

AC Code

/** * 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)// In the sequence traversal 
    {
    
        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);
    }
};