36剑指offer 二叉搜索树与双向链表

题目描述

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

由于要求转换成一个排序的双向链表，因为二叉搜索树的中序遍历就是有序的，因此遍历过程中可以使用中序遍历。

分析与解法： 

首先 我们知道：在二叉树中，每个结点都有两个指向子结点的指针。在双向链表中，每个结点也有两个指针，它们分别指向前一个结点和后一个结点。

观察根结点的左子树，再观察已转换好的双向链表的左子树部分。只需将4与6的双向链表转换好，其余部分按中序递归即可。

双向链表转换思想：

当遍历到4时，我们需要使4->left=6,6->right=4;而且需要更新双向链表的最后一个结点，以便后面双向链表的建立。因此需要引入一个新的结点pLastNodeInList。

 使用情况看代码：

class Solution {
public:
   
    TreeNode* Convert(TreeNode* pRootfTree)
    {
        if(pRootOfTree==NULL)
            return pRootOfTree;
        TreeNode*lastnodeinlist=NULL;
        convertnode(pRootOfTree,&lastnodeinlist);
        TreeNode*headnode=lastnodeinlist;
        while(headnode->left)
            headnode=headnode->left;
        return headnode; 
    }
      void convertnode(TreeNode*root,TreeNode**lastnodeinlist)
    {
         if(root==NULL)
             return;
       ////中序遍历
        TreeNode*cur=root;
     //遍历左子树
         if(cur->left)
           convertnode(cur->left,lastnodeinlist);
 //原先指向左子结点的指针调整为链表中指向前一个结点的指针
          cur->left=*lastnodeinlist;//开始时4->left=NULL,主函数中寻找头结点正是利用了这里的NULL.
//原先指向右子结点的指针调整为链表中指向下一个结点的指针
         if(*lastnodeinlist!=NULL)
             (*lastnodeinlist)->right=cur;
           *lastnodeinlist=cur;
    //遍历右子树
         if(cur->right!=NULL)
            convertnode(cur->right,lastnodeinlist);  
    }
};

函数调用详细流程图：