/*

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;

    }

};