非递归的方法(c++)

语言：C++
思路：大家普遍的解法是中序遍历+递归，这种方法主要抓住了二叉搜索树的中序遍历结果是有序的特点！
但这里提供一种非递归的方法，这种方法借鉴于平衡二叉树的单旋转方法，目标是把这个二叉搜索树变成一个简易二叉搜索树(这里的简易二叉树是我杜撰的概念，它指根节点的左边没有右子树，根节点的右边没有左子树）。图示说明如下，对于每个二叉搜索树(例如图左)，如果通过一定方法将它变为简易二叉搜索树(例如图中)，那么自然也就是有序的双向链表(图右)。

下面说说怎么将普通二叉搜索树变为简易二叉搜索树，这里借鉴了平衡二叉树中的单旋转方法。举个例子，对于根节点10来说，在它左边的数显然应该是8，右边的数是12。那么8和12分别具有什么样的特点呢？观察可以看出，8是根节点10的左子树的最右边的节点，而12是根节点10的右子树的最左边的结点。那么现在如果我令10的左指针指向8，右指针指向12，再让剩余的左子树和右子树的部分续接在8和12两个节点上。就可以实现节点8，10，12的有序性，以此方法往下就可以得到一个简易二叉搜索树。具体的实现方式见代码
算法效率： 时间O(n); 空间O(1)。(时间上的算法效率是粗略估计，不一定准确)
具体代码：

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if (pRootOfTree == nullptr) return nullptr;

        TreeNode* pRoot = pRootOfTree;
        // 先处理pRootOfTree的右子树
        while (pRootOfTree->right)
        {
            TreeNode* p_right = pRootOfTree->right;
            if (p_right->left == nullptr) 
            {
                p_right->left = pRootOfTree;
                pRootOfTree = p_right;
            }
            else
            {
                TreeNode* p_3 = p_right;
                TreeNode* p_4 = p_3->left;
                while (p_4->left)
                {
                    p_3 = p_4;
                    p_4 = p_4->left;
                }
                p_3->left = nullptr;
                pRootOfTree->right = p_4;
                p_4->left = pRootOfTree;
                while (p_4->right)
                    p_4 = p_4->right;
                p_4->right = p_right;

                pRootOfTree = pRootOfTree->right;
            }
        }
        // 处理pRootOfTree的左子树
        while (pRoot->left)
        {
            TreeNode* p_left = pRoot->left;
            if (p_left->right == nullptr) 
            {
                p_left->right = pRoot;
                pRoot=p_left;
            }
            else
            {

                TreeNode* p_1 = pRoot->left;
                TreeNode* p_2 = p_1->right;
                while (p_2->right)
                {
                    p_1 = p_2;
                    p_2 = p_2->right;
                }
                p_1->right = NULL;
                pRoot->left = p_2;
                p_2->right = pRoot;
                while (p_2->left)
                    p_2 = p_2->left;
                p_2->left = p_left;

                pRoot = pRoot->left;
            }
        }
        //pRoot此时就是头节点
        return pRoot; 
    }
};