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

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

方法一： 链接：https://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5 来源：牛客网 递归版 解题思路： 1.将左子树构造成双链表，并返回链表头节点。 2.设置一个新的数据成员leftlast记录左子树的最后一个节点。 3.如果左子树链表不为空的话，将当前root追加到左子树链表。 4.将右子树构造成双链表，并返回链表头节点。 5.如果右子树链表不为空的话，将该链表追加到root节点之后。 6.根据左子树链表是否为空确定返回的节点。

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { TreeNode* leftlast; public: TreeNode* Convert(TreeNode* pRootOfTree) { if (!pRootOfTree) return NULL; TreeNode* leftSubList = Convert(pRootOfTree->left); if (leftSubList) { pRootOfTree->left = leftlast; leftlast->right = pRootOfTree; } leftlast = pRootOfTree; TreeNode* rightSubList = Convert(pRootOfTree->right); pRootOfTree->right = rightSubList; if(rightSubList) rightSubList->left = pRootOfTree; return !leftSubList ? pRootOfTree : leftSubList; } };

方法二： 解题思路： 1.核心是中序遍历的非递归算法。 2.修改当前遍历节点与前一遍历节点的指针指向。

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: TreeNode* Convert(TreeNode* pRootOfTree) { if (!pRootOfTree) return NULL; TreeNode* listHead; TreeNode* currentNode = pRootOfTree; TreeNode* pre = NULL; stack<TreeNode*> assistStack; while (currentNode || !assistStack.empty()) { while (currentNode) { assistStack.push(currentNode); currentNode = currentNode->left; } currentNode = assistStack.top(); assistStack.pop(); currentNode->left = pre; if(pre) pre->right = currentNode; else listHead = currentNode; pre = currentNode; currentNode = currentNode->right; } return listHead; } };

方法三： 思路：使用队列。 先将二叉搜索树的中序遍历序列存储在队列中，之后再依次出队，将处理左右指针的指向即可。 注意：在队列中存储的是TreeNode*，不是节点的val值。

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { queue<TreeNode*> sortedNodes; void InOrder(TreeNode* pRootOfTree){ if(pRootOfTree){ InOrder(pRootOfTree->left); sortedNodes.push(pRootOfTree); InOrder(pRootOfTree->right); } } public: TreeNode* Convert(TreeNode* pRootOfTree) { if(!pRootOfTree) return pRootOfTree; InOrder(pRootOfTree); TreeNode* listHead = sortedNodes.front(); TreeNode* assistant = listHead; sortedNodes.pop(); while(!sortedNodes.empty()){ sortedNodes.front()->left = assistant; assistant->right = sortedNodes.front(); assistant = sortedNodes.front(); sortedNodes.pop(); } return listHead; } };