给你一棵二叉搜索树,请你 按中序遍历 将其重新排列为一棵递增顺序搜索树,使树中最左边的节点成为树的根节点,并且每个节点没有左子节点,只有一个右子节点。
图片说明
二叉树的题要记得保存好头指针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);
    }
};