/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    void converTree(TreeNode * pTree, TreeNode *&prev)    //二級指針 = 指針引用  (降級，可以直接用pre操作，否則要*pre)
    {
        if(pTree == nullptr)
        {
            return ;
        }
        converTree(pTree->left, prev);
        
        pTree->left = prev;
        if(prev != nullptr)
        {
            prev->right = pTree;
        }
        prev = pTree;
        
        converTree(pTree->right, prev);
    }
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree == nullptr)
        {
            return nullptr;
        }
        TreeNode *pTree = nullptr;
        //轉化
        converTree(pRootOfTree,pTree);
        //輸出頭節點
        TreeNode *ret = pRootOfTree;
        while(ret->left != nullptr)
        {
            ret = ret->left;
        }
        return ret;
    }
};