【 声明：版权所有，转载请标明出处，请勿用于商业用途。 联系信箱：libin493073668@sina.com】
题目链接：?rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。思路在二叉搜索树中，对于一个结点而言，其左子树必然都是小于根节点与右子树的，而右子树必然都是大于左子树与根节点的，那么我们在遍历的过程中，先从根节点一直遍历到最左的结点，然后再回溯的时候再遍历右子树。
/*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){TreeNode* pLastNode = nullptr;CovertNode(pRootOfTree,&pLastNode);TreeNode* pHeadNode = pLastNode;while(pHeadNode!=nullptr && pHeadNode->left!=nullptr){pHeadNode = pHeadNode->left;}return pHeadNode;}void CovertNode(TreeNode* pNode,TreeNode** pLastNode){if(pNode==nullptr) return;TreeNode* pCur = pNode;if(pCur->left!=nullptr)CovertNode(pCur->left,pLastNode);pCur->left = *pLastNode;if(*pLastNode!=nullptr)(*pLastNode)->right = pCur;(*pLastNode) = pCur;if(pCur->right!=nullptr)CovertNode(pCur->right,pLastNode);}};
版权声明：本文为博主原创文章，，如果转载，请注明出处
放手后的微笑，只是用来掩盖疼痛的伤疤…
