LeetCode 897. 递增顺序查找树（中序遍历）

示例 ：

输入：[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  

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;
    }
};