[剑指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; } };

 

转载于:https://www.cnblogs.com/ruoh3kou/p/10080648.html