题目
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
解题思路
本题的实质是二叉搜索树的中序遍历,附带双向链表的构建。我采取的方法是先获取搜索树的中序遍历,存取各结点的指针,然后构建双向链表。二叉搜索树的中序遍历我采用的是Morris算法,关于Morris算法,CSDN中有篇博文讲的很详细,链接如下:Morris算法进行二叉树遍历 ,各位可前往了解。
代码
/* 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) { vector<TreeNode*> ret; if (pRootOfTree == NULL) { return pRootOfTree; } TreeNode *curr = pRootOfTree; TreeNode *pre,*next; TreeNode *head; while(curr) { if(curr->left==NULL) { ret.push_back(curr); curr=curr->right; } else { pre=curr->left; while(pre->right&&pre->right!=curr) { pre=pre->right; } if(pre->right==NULL) { pre->right=curr; curr=curr->left; } else { ret.push_back(curr); pre->right=NULL; curr=curr->right; } } } head = ret[0]; head->left = NULL; if (ret.size() == 1) { head->right = NULL; } else { for (int j = 0; j < ret.size() - 1; j++) { curr = ret[j]; next = ret[j+1]; curr->right = next; next->left = curr; } next->right = NULL; } return head; } };