面试题36：二叉搜索树与双向链表

题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

（这道题真的很考察思路、代码其实不是很难，就是指针很多，容易眼花，所以真的是质量很高的一道题）

思路

1、因为是二叉搜索树，所以左子树比根值小，右子树比根值小，这就是一个突破口
2、那自然想到我们排序的值应按先左子树再根再右子树，所以就用到中序遍历
3、采用递归就可以很好地解决问题

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree==nullptr)
            return nullptr;
        TreeNode* lastnode = nullptr;
        TreeNode*headnode = convertnode(pRootOfTree,lastnode);
        while(headnode!=nullptr&&headnode->left!=nullptr)
        //一直从根向左遍历就可以找到左子树的最左节点，就二十最小值
            headnode = headnode->left;
        return headnode;
    }
    TreeNode* convertnode(TreeNode* root,TreeNode* lastnode)
    {
        if(root == nullptr)
            return nullptr;
        if(root->left!=nullptr)//先遍历左子树
            lastnode = convertnode(root->left,lastnode);
        root->left = lastnode;
        //左子树遍历完之后，根的左边最近节点就是遍历完左子树的最后一个节点
        
        //这个if判断语句千万不能漏掉
        //如果漏掉，左子树就不会和根连接，就会断链的！！！
        if(lastnode!=nullptr)
            lastnode->right = root;
        lastnode = root;//左子树已经遍历完了，最后一个节点自然而然就变成了根了
        if(root->right!=nullptr)//右子树遍历
            lastnode = convertnode(root->right,lastnode);
        return lastnode;
    }
};