897. 递增顺序搜索树

描述

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

示例 1：
输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

示例 2：
输入：root = [5,1,7]
输出：[1,null,5,null,7]

code

参考中序遍历

class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        TreeNode* head = new TreeNode();
        TreeNode* hair = new TreeNode();
        head->right = hair;
        TreeNode* cur = root;
        stack<TreeNode*> st;
        while(cur!=nullptr || !st.empty()){
            while(cur!=nullptr){
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            st.pop();
            hair->right = cur;
            hair = hair->right;
            cur->left = nullptr;
            cur = cur->right;
        }
        return head->right->right;
    }
};