二叉搜索树与双向链表
题目描述：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
解题思路：
- 这道题目本质上就是BST的线索化，具体的操作步骤如下：
- 线索化根结点的左子树
- 将左子树的尾节点指向根结点
- 线索化根结点的右子树
- 将根结点指向右子树的头结点
- 若有左子树，则返回左子树的头结点；若没有，则返回根结点
代码：
class Solution{
public:
TreeNode* Convert(TreeNode *root) {
if (root == nullptr)
return nullptr;
// 如果root为叶子结点，没有左右子树
// 则返回root本身
if (root->left == nullptr && root->right == nullptr)
return root;
TreeNode *leftHead = nullptr, *leftNode = nullptr;
TreeNode *rightHead = nullptr;
// 如果左子树不为空，则线索化左子树
if (root->left != nullptr) {
leftHead = Convert(root->left);
}
// 找到左子树的尾节点
leftNode = leftHead;
while (leftNode != nullptr && leftNode->right != nullptr) {
leftNode = leftNode->right;
}
// 将尾节点的右指针指向root结点
// 将root结点的左指针指向leftTail
// 在这里leftNode已经等于leftTail
if (leftNode != nullptr) {
leftNode->right = root;
root->left = leftNode;
}
// 线索化右子树
if (root->right != nullptr) {
rightHead = Convert(root->right);
}
// 将root的右指针指向rightHead
// 将rightHead的左指针指向root
if (rightHead != nullptr) {
root->right = rightHead;
rightHead->left = root;
}
// 如果左子树不为空，返回leftHead
// 如果左子树为空树，则返回root
return leftHead == nullptr ? root : leftHead;
}
};
2018.10.19
