[数据结构与算法]剑指offer - 二叉搜索树与双向链表

题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

算法思路

其实就是线索化二叉树的变形。

需要明白的一点就是，二叉搜索树的中序遍历是有序的。也就是说，这道题的大体框架就是使用中序遍历，然后在中序遍历的过程中，构建前驱和后继节点。

1. 定义一个前驱指针，保存前驱节点
2. 中序遍历二叉搜索树，注意前驱节点空和不为空的情况，只有前驱节点不为空的情况下，才可以指向后继节点。移动前驱指针指向当前节点，让当前节点变为前驱节点
3. 根据题目，是否要求首尾指针要相连，如果需要，则要构建首尾指针的关系

代码实现

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    Node pre,head;
    public Node treeToDoublyList(Node root) {
        if(root==null) return null;
        //中序遍历
        Inorder(root);
        //这两行的代码是尾节点后继指向头节点，头节点前驱指向尾节点，看题目要求，如果题目要求首尾节点要相互指向的话，就写上去
        //pre.right = head;
        //head.left = pre;
        return head;
    }
	//中序遍历
    private void Inorder(Node cur){
        if(cur==null) return;
        Inorder(cur.left);
        //逻辑处理过程
        //如果前驱节点不为空，前驱节点的后继就是当前节点
        if(pre!=null){
            pre.right = cur;
        }else{//如果为空的话，说明当前节点就是头节点
            head = cur;
        }
        //不管前驱节点是否为空，当前节点的左指针都是指向前驱节点的
        cur.left = pre;
        //移动指针，当前节点变成了前驱节点
        pre = cur;
        Inorder(cur.right);
    }
}