剑指Offer第26题：二叉搜索树与双向链表

发表于 更新于 分类于

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

解题思路：二叉搜索树的中序遍历为有序序列，因此在二叉树的中序遍历时修改指针的指向即可。创建一个全局的指针用于记录先前的结点。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void ConvertHelper(TreeNode* root, TreeNode* &pre) { // pre需要用引用传递
    if (root) {
        ConvertHelper(root->left, pre);
        root->left = pre;
        if (pre) pre->right = root; //注意需要先判断pre是否为空
        pre = root;
        ConvertHelper(root->right, pre);
    }
}
TreeNode* Convert(TreeNode* pRootOfTree) {
    if (!pRootOfTree) return NULL; //先判断pRootOfTree是否为空
    TreeNode* pre = NULL; 
    ConvertHelper(pRootOfTree, pre);
    while (pRootOfTree->left) //寻找树的最左下结点
        pRootOfTree = pRootOfTree->left;
    return pRootOfTree;
}