给定一个树,按中序遍历重新排列树,使树中最左边的结点现在是树的根,并且每个结点没有左子结点,只有一个右子结点。
示例 :
输入:[5,3,6,2,4,null,8,1,null,null,null,7,9]
5
/ \
3 6
/ \ \
2 4 8
/ / \
1 7 9
输出:[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
1
\
2
\
3
\
4
\
5
\
6
\
7
\
8
\
9
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/increasing-order-search-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
TreeNode* increasingBST(TreeNode* root) {
bool getroot = false;
stack<TreeNode*> stk;
TreeNode *newroot, *prev, *cur;
while (root || !stk.empty())
{
while(root)
{
stk.push(root);
root = root->left;
}
root = stk.top();
if(!getroot)
{
newroot = new TreeNode(root->val);
prev = newroot;
getroot = true;
}
else
{
cur = new TreeNode(root->val);
prev->right = cur;
prev = cur;
}
stk.pop();
root = root->right;
}
return newroot;
}
};