/*

题目：

	将二叉搜索树转化为排序的双向链表，不能创建新的节点，

	只能调整节点的指向，返回双向链表的头节点。

*/

/*

思路：

	递归。

	二叉搜索树的中序遍历得到的序列是递增序列。

	左子树left<=>root<=>右子树right。

	左链表left<=>root<=>右链表right。

	对于左链表，我们需要它的最后一个节点；对于右链表，我们需要它的第一个节点。

	我们设置一个公共节点表示lastNode，函数返回firstNode。

	将root节点跟在做链表后，将右链表跟在root节点之后，则得到最终结果。

*/

#include<iostream>

#include<string.h>

#include<algorithm>

#include<cmath>

#include<stdio.h>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

struct TreeNode {

	int val;

	struct TreeNode *left;

	struct TreeNode *right;

	TreeNode(int x) :

			val(x), left(NULL), right(NULL) {

	}

};

TreeNode* lastNode = nullptr;

TreeNode* Convert(TreeNode* pRootOfTree)

{

    if(pRootOfTree == nullptr || (pRootOfTree->left == nullptr && pRootOfTree->right == nullptr)) {

       lastNode = pRootOfTree;

       return pRootOfTree;

    }

    TreeNode* left = Convert(pRootOfTree->left);

    if(left != nullptr){

        lastNode->right = pRootOfTree;

        pRootOfTree->left = lastNode;

    }

    TreeNode* right = Convert(pRootOfTree->right);

    if(right != nullptr){

        pRootOfTree->right = right;

        right->left = pRootOfTree;

    }

    lastNode = (right == nullptr) ? pRootOfTree : right;

    return (left == nullptr)? pRootOfTree : left;

}