- 题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
- 题目解析
其实就是中序遍历。
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
if (pRootOfTree == NULL)
return pRootOfTree;
pRootOfTree = ConvertCore(pRootOfTree);
while (pRootOfTree->left)
pRootOfTree = pRootOfTree->left;
return pRootOfTree;
}
TreeNode* ConvertCore(TreeNode* root){
if (root == NULL)
return root;
if (root->left != NULL){
TreeNode* left = ConvertCore(root->left);
while (left->right)
left = left->right;
left->right = root;
root->left = left;
}
if (root->right != NULL){
TreeNode* right = ConvertCore(root->right);
while (right->left)
right = right->left;
right->left = root;
root->right = right;
}
return root;
}
};