题解 | #二叉搜索树与双向链表#

观察容易发现双向链表的顺序与该二叉树中序遍历的结果相同。故首先考虑中序遍历解题。
最开始由于题目中要求空间复杂度为O(1)，故考虑原地操作，但递归的中序遍历也需要用到递归栈，如果真的要满足空间复杂度为O(1)，则需要考虑迭代中序遍历树，或放弃中序遍历的思路。
这里最终还是选择使用中序遍历，将结点按中序遍历的顺序插入数组，然后遍历数组依此修改左右指针。
这里需要注意中序遍历的顺序十分重要，必须是先左子树后右子树，否则就算在遍历数组中反转左右指针，一样会出错。

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    vector<TreeNode*> arr;
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(!pRootOfTree){
            return pRootOfTree;
        }
        change(pRootOfTree);
        arr.front()->left = nullptr;
        arr.back()->right = nullptr;
        for (int i = 0; i < arr.size()-1; ++i){
            arr[i]->right = arr[i+1];
            arr[i+1]->left = arr[i];
        }
        return arr.front();
    }
    void change(TreeNode* &p){
        if(p->left){
            change(p->left);
        }
        if(p){
            arr.push_back(p);
        }
        if(p->right){
            change(p->right);
        }
    }
};