题目描述

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

解题思路

convertHelper 函数考虑了树的 5 种形态：

代码实现

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { private: void convertHelper(TreeNode* currNode, TreeNode*& lastNodeOfLeftSubtreeLink){ // 递归的结束条件 if(currNode == NULL) return; // 递归 // L convertHelper(currNode->left, lastNodeOfLeftSubtreeLink); // D currNode->left = lastNodeOfLeftSubtreeLink; if(lastNodeOfLeftSubtreeLink) lastNodeOfLeftSubtreeLink->right = currNode; lastNodeOfLeftSubtreeLink = currNode; // R convertHelper(currNode->right, lastNodeOfLeftSubtreeLink); } public: TreeNode* Convert(TreeNode* pRootOfTree) { // 函数参数的合法性判断 if(pRootOfTree == NULL) return NULL; // 转换成排序的双向链表 TreeNode* lastNodeOfLeftSubtreeLink = NULL; convertHelper(pRootOfTree, lastNodeOfLeftSubtreeLink); // 寻找链表的表头并返回表头值 TreeNode* pHead = pRootOfTree; while(pHead->left) pHead = pHead->left; return pHead; } };

运行结果

运行时间：4ms 占用内存：476k