二叉搜索树与双向链表

题目描述

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

问题分析

二叉搜索树是一种排序的数据结构，每个结点都有两个指向子结点的指针。在双向链表中，每个结点也有两个指针，他们分别指向前一个结点和后一个结点。在二叉搜索树中，左子结点的值总是小于父结点的值，右子结点的值总是大于父结点的值。因此我们在转换成排序双向链表时，原先指向左子结点的指针调整为链表中指向前一结点的指针，原先指向右子结点的指针调整为链表中指向后一个结点指针。

中序遍历在二叉搜索树中的特点是按照从小到大的顺序遍历二叉树的每一个结点。下图中，我们可以把树分成三个部分：值为10的结点、根结点为6的左子树、根结点为14的右子树。根绝排序链表的定义，值为10的结点将和它的左子树的最大一个结点链接起来，同时它还将和右子树最小的结点链接起来。

示例

解题思路1

/*
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 == NULL)
            return NULL;
        if(pRootOfTree->left == NULL && pRootOfTree->right == NULL)
            return pRootOfTree;
        //遍历左子树
        TreeNode* pLeft = Convert(pRootOfTree->left);
        TreeNode* pCurrent = pLeft;
        //定位至左子树最右的一个结点
        while(pCurrent != NULL && pCurrent->right != NULL)
            pCurrent = pCurrent->right;
        //如果左子树不为空，则将当前pRootOfTree加到左子树链表
        if(pLeft != NULL){
            pCurrent->right = pRootOfTree;
            pRootOfTree->left = pCurrent;
        }
        //遍历右子树
        TreeNode* pRight = Convert(pRootOfTree->right);
        //如果右子树不为空，则将当前pRootOfTree加到右子树链表
        if(pRight != NULL){
            pRight->left = pRootOfTree;
            pRootOfTree->right= pRight;
        }
        
        return pLeft != NULL?pLeft:pRootOfTree;
    }
};