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

题目：二叉搜索树与双向链表

描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

注意:

1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

4.你不用输出或者处理，示例中输出里面的英文，比如"From left to right are:"这样的，程序会根据你的返回值自动打印输出

示例:

输入: {10,6,14,4,8,12,16}

输出:From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;

题目解析: 系统自动输入一颗二叉树，输出的时候将双向链表从左往右输出和从右往左输出，在输出过程中要确保答案的正确性。

解题思路：对于二叉搜索树来说，中序遍历输出的数值为升序排列。所以我们需要通过中序遍历去解决问题，因为输出的链表是从左往右输出，从左往右依次增大，我们按照正常思路来思考问题，就是将根节点的左（前）指向根节点左子树的最大值，将根节点的右（后）指向根节点右子树的最小值，若左子树或者右子树只有两层的话，直接将左子树或者右子树按照中序遍历输出即可。

采用递归操作解决问题，递归操作的条件为，当二叉树遍历遇到子节点为不存在的情况时就不会继续往下遍历，即终止本轮递归。总体思想是借用中序遍历，实现递归。

具体C++代码如下所示：

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
    TreeNode* preNode = nullptr;
public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(pRootOfTree == nullptr)
            return nullptr;
        Convert(pRootOfTree->right);//找到最右边的节点
        if(preNode != nullptr){
            pRootOfTree->right = preNode;
            preNode->left = pRootOfTree;
        }
        preNode = pRootOfTree;
        Convert(pRootOfTree->left);
        return preNode;
    }
};

按照代码要求，首先执行的是最后一层的右结点，将右节点与右节点根结点之间构建连接，然后按照递归思想，一直循环执行即可完成目标输出。

另一种解法：在二叉树中，每个结点都有两个指向子结点的指针，双向链表中也存在，在搜索二叉树中左结点的值总是小于父结点的值，右结点的值总是大于父结点的值。在转换成排序双向链表时，原先指向左结点的指针调整为链表中指向前一个结点的指针，原先指向右结点的指针调整为链表中指向后一个结点的指针。

C++代码如下所示：

/*
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) {
        TreeNode* pNode = NULL;
        List(pRootOfTree,&pNode);
        TreeNode* pHead = pNode;
        while (pHead != NULL && pHead->left != NULL)
            pHead = pHead->left;
        return pHead;
    }
    void List(TreeNode* Root,TreeNode**pr){
        if (Root == NULL)
            return ;
        TreeNode* pc = Root;
        if(pc->left != NULL)//递归左子树
            List(pc->left,pr);
        pc->left = *pr;
        if(*pr != NULL)
            (*pr)->right = pc;
        *pr = pc;
        if(pc->right != NULL)
            List(pc->right,pr);
        }
};