本文共 1176 字，大约阅读时间需要 3 分钟。

剑指offer——面试题27：二叉搜索树与双向链表

Solution1:

class Solution {public:    TreeNode* Convert(TreeNode* pRootOfTree) {        TreeNode *pLastNodeInList = NULL;        ConvertNode(pRootOfTree, pLastNodeInList);        //pLastNodeInList指向双链表的尾结点        //返回头结点        TreeNode *pHeadOfList = pLastNodeInList;        while(pHeadOfList && pHeadOfList->left)            pHeadOfList = pHeadOfList->left;        return pHeadOfList;    }    void ConvertNode(TreeNode* pNode, TreeNode *&pLastNodeInList){ //第二个参数是指针的引用        if(!pNode)            return;        TreeNode *pCurrent = pNode;  //pNode目前指向的根结点，把pCurrent初始化为指向此根节点        if(pCurrent->left)   //如果根结点的左子树非空，则去处理左子树            ConvertNode(pCurrent->left, pLastNodeInList);        pCurrent->left = pLastNodeInList;//把左子树中值最大的结点的位置赋值给当前根结点的左指针        if(pLastNodeInList)            pLastNodeInList->right = pCurrent;//相应的根结点的位置赋给左子树中值最大结点的右指针                                              //经过这两步就把当前的根结点串到双向链表中了        pLastNodeInList = pCurrent;           //所以，这一步就更新链表中尾结点的位置，设为当前根结点的位置        if(pCurrent->right)           //右子树非空，处理右子树去。。            ConvertNode(pCurrent->right,pLastNodeInList);    }};

转载地址：http://nxhdb.baihongyu.com/