题解 | #二叉搜索树与双向链表#

jz 26

题意描述

题目大意：将二叉搜索树转换成一个双向链表

基础知识：二叉搜索树（BST），它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。二叉搜索树的示例图如下：

图片说明

在结点4的位置看其左孩子(2)和其右孩子(4)。左孩子(2)小于根结点4，右孩子(5)大于根节点4。树中的其他结点满足同样的要求。

中序遍历:为对二叉树作 “左、根、右” 顺序遍历，递归伪代码实现如下：

dfs(root):
    if(root==NULL) then return
    dfs(root->left)  # 左
       visit(root)
    dfs(root->right) # 右

对BST进行中序遍历，会得到一个有序的序列，如对上面示例的BST进行中序遍历，会得到1->2->3->4->5的有序序列。

双向链表：链表中的每一个结点与它的前驱结点和后驱结点均有指针相连，双向链表如下图所示。

图片说明

题解一：

针对本题：直接的想法是对BST中序遍历。遍历到了最左叶子结点（最小的值）时，开始新建一个双向链表，然后把后续遍历到的结点追加到新建的链表中。

这么做很navie，使用了额外空间，不符合本题要求。

题解二：

本题要求我们改变树中的结点的指针指向，来生成目标双向链表。同解法一，对BST进行中序遍历，在中序遍历时改变树中结点指向即可。

针对如上所给BST，转换成双向链表的过程：如下图所示
图片说明

写成代码：

    TreeNode *pre, *head;
    void dfs(TreeNode* cur) {
        if(cur == nullptr) return;
        dfs(cur->left);
        if(pre !=nullptr) {
            pre->right = cur;
        }
        else{
            head = cur;
        }
        cur->left = pre;
        pre = cur;
        dfs(cur->right);
    }
    TreeNode* Convert(TreeNode* root) {
        if(!root) return nullptr;
        dfs(root);
        pre->right = nullptr;
        return head;
    }

时间复杂度： $O(N)$ ，N为BST中的结点树，我们只对BST进行了一次遍历。

空间复杂度： $O(h)$ ，h为树深。中序遍历可以看做是递归调用。递归调用栈的大小与BST的树深成线性关系。