[剑指offer] 26. 二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路：
利用中序遍历的特性，从小到大遍历二叉树每一个结点。
修改中序遍历，在在其中加入一个前驱结点
遍历左子树
前驱结点右指针指向当前结点
当前结点指向左指针指向前驱结点
前驱 = 当前
遍历右子树
此时遍历结果pre指针指向的是链表尾，如果将上面的左右反过来，则直接返回pre即正确的答案。
class Solution { public: TreeNode *preNode = NULL; TreeNode *Convert(TreeNode *curNode) { if (curNode == NULL) return NULL; Convert(curNode->right); if (preNode) { preNode->left = curNode; curNode->right = preNode; } preNode = curNode; Convert(curNode->left); return preNode; } };