Leetcode-递增顺序搜索树（简单）

给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

二叉树的题要记得保存好头指针result，用新的指针ans复制后去遍历，防止遍历影响头指针

设立result作为结果的头指针，然后ans等于它；
ans的右指针等于root，将root的左孩子设置为空，并成为新的ans

TreeNode* increasingBST(TreeNode* root) {
        TreeNode* result=new TreeNode(0);
        ans=result;//ans负责递归往后接，result永远指向最初节点
        inroder(root);
        return result->right;
    }
    void inroder(TreeNode* root){
        if(root==nullptr) return;
        inroder(root->left);
        ans->right=root;
        root->left=nullptr;//root左孩子置空
        ans=root;
        inroder(root->right);
    }

或者 在dfs函数里重新节点（时间最短）

    void inroder(TreeNode* root){
        if(root==nullptr) return;
        inroder(root->left);
        ans->right=new TreeNode(root->val);//root的值作为新的节点的值
        ans=ans->right;
        inroder(root->right);
    }
};

另一种，普通中序遍历，然后每次把val放进数组
通过数组数据重建二叉树

class Solution {
public:
    vector<int> temp;
    TreeNode* increasingBST(TreeNode* root) {
        inroder(root);
        TreeNode* result=new TreeNode(0);
        TreeNode* ans=result;//用ans进行循环，保留住result的位置
        for(auto i:temp){
            ans->left=nullptr;
            ans->right=new TreeNode(i);
            ans=ans->right;
        }
        return result->right;
    }
    void inroder(TreeNode* root){
        if(root==nullptr) return;
        inroder(root->left);
        temp.push_back(root->val);
        inroder(root->right);
    }
};