/*
题目：
	将二叉搜索树转化为排序的双向链表，不能创建新的节点，
	只能调整节点的指向，返回双向链表的头节点。
*/
/*
思路：
	递归。
	二叉搜索树的中序遍历得到的序列是递增序列。
	左子树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;

}