剑指offer_【26】二叉搜索树与双向链表

1. 题目描述

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

二叉树如

             10

         /        \

      6            14

   /     \       /      \

4         8    12        16

转化成双向链表 4 <----> 6 <----> 8 <----> 10 <---->12 <---->14<---->16

2.解题思路

(1)二叉搜索树中，每个结点都有两个分别指向其左、右子树的指针，左子树结点的值总是小于父结点的值，右子树结点的值总是大于父结点的值。

(2)双向链表中，每个结点也有两个指针，它们分别指向前一个结点和后一个结点。所以这两种数据结构的结点是一致
为了减少指针的变换次数，并让操作更加简单，在转换成排序双向链表时，原先指向左子结点的指针调整为链表中指向前一个结点的指针，原先指向右子结点的指针调整为链表中指向下一个结点的指针。

链表是有序的，可以借助二叉树中序遍历，因为中序遍历算法的特点就是从小到大访问结点。当遍历访问到根结点时，假设根结点的左侧已经处理好，只需将根结点与上次访问的最近结点（左子树中最大值结点）的指针连接好即可。进而更新当前链表的最后一个结点指针。同时中序遍历过程正好是转换成链表的过程，可采用递归方法处理

思想：把左子树、右子树都转换成排序的双向链表之后在和根结点链接起来，整个二叉树也变成了排序的双向链表。

3. 代码

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public TreeNode Convert(TreeNode root) {
       if(root==null){//假如根节点为空，返回空
        return null;
    }
    if(root.left==null&&root.right==null){//假如只有一个根节点，则返回根节点
        return root;
    }
    //1、将左子树构造成双链表，并返回该链表头结点left
    TreeNode left=Convert(root.left);
    //2、定位到左子树链表的最后一个节点（左子树最右边的节点）
    //创建一个临时节点P,用来遍历找到左链表的最后一个节点(左子树最右边的节点)，p初始化指向做左子树的根节点，
    TreeNode p=left;
    while(p!=null&&p.right!=null){
        //最终p为左子树最右边的节点
        p=p.right;
    }
    //3、如果左子树链表不为空，将当前root追加到左子树链表后 
    if(left!=null){//左子树链表不为空
       //左子树链表的最后一个节点p（左子树最右边节点）的右指针指向当前root节点
        p.right=root;
       //当前root节点的左指针指向左子树链表的最后一个节点p（左子树最右边节点）
        root.left=p;
    }
    //4、将右子树构造成双链表，并返回该链表的头结点right
    TreeNode right=Convert(root.right);
    //5、如果右子树链表不为空，将右子树链表追加到当前root后
    if(right!=null){//右子树链表不为空
        right.left=root;//右子树链表的头结点right的左指针指向当前root
        root.right=right;//当前root的右指针指向右子树链表的头结点right
    }
    return left!=null?left:root;//根据左子树链表是否为空返回整个双向链表的头指针。    
    }
}