描述
給你一棵二叉搜索樹关翎，請(qǐng)你 按中序遍歷 將其重新排列為一棵遞增順序搜索樹负拟，使樹中最左邊的節(jié)點(diǎn)成為樹的根節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)沒有左子節(jié)點(diǎn)脚仔，只有一個(gè)右子節(jié)點(diǎn)勤众。
示例 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;
}
};
