牛客网：二叉搜索树与双向链表

麻，这也是递归思想，中序遍历的一个好题。

考虑几个问题：

1.我们如何确定表头节点

2.我们如何补上剩下的指针

第一个问题：

双向链表的遍历是根据中序遍历得到的，我们很自然想到一直往左走，这很容易想到我们要的表头其实是从根往左走的第一个叶子节点，那我们也很容易想到一直递归root->left，那又有问题了，我们如何判定这是个叶子节点呢？设置flag遇到第一个左右子树都为NULL的节点？这样是有点呆的。不过可行。

再转念一想，如果我们遇到一个空的节点要把他转化为双向链表如何去做？没错返回NULL就行。那接着想，我们如果一直往左走，遇到了一个空的NULL返回的第一个节点不就是头么，没错，我们先设置一个空的head指针，然后让函数一直往左子树递归，接着写上一个判断head是否为空的判断，是则当前节点就是我们要找的表头。

第二个问题：

我们设置一个pre指针记录之前访问过的节点，我们希望这个指针是这样的：

 那操作不就很简单，pre->right=p,p->left=pre,然后更新pre=p，问题是我们如何维持这样一个访问状态？首先在初始化的时候pre=NULL,这也很好理解，头节点前面没有东西嘛。那当我们在找到表头的同时把pre也更新为表头，这pre不就有值了么，然后再在补全指针的同时更新pre，双向链表就出来了。

具体代码如下所示：

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
private:
    TreeNode *pre=NULL;
    TreeNode *head=NULL;
public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(pRootOfTree==NULL){
            return NULL;
        }
        Convert(pRootOfTree->left);
        //从最左节点返回 据此设定头节点以及最初的pre
        if(pre==NULL){
            head=pRootOfTree;
            pre=pRootOfTree;
        }else{//说明已经存在pre
            pre->right=pRootOfTree;
            pRootOfTree->left=pre;
            pre=pRootOfTree;
        }
        Convert(pRootOfTree->right);
        return head;
    }
};