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

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

解答：
1.思路：添加一个数组存放中序遍历的结果。

public class Q_26 {

List<TreeNode> list=new ArrayList<>();
public TreeNode Convert(TreeNode pRootOfTree) {
    if(pRootOfTree==null){
        return null;
    }
    MidSort(pRootOfTree);
    return mangeList();
}
public void MidSort(TreeNode pRootOfTree) {
    if (pRootOfTree == null) {
        return;
    }
    MidSort(pRootOfTree.left);
    list.add(pRootOfTree);
    MidSort(pRootOfTree.right);
}
public TreeNode mangeList() {
    TreeNode pre = list.get(0);
    TreeNode tmp;
    for (int i = 1; i < list.size(); i++) {
        tmp = list.get(i);
        tmp.left = pre;
        pre.right = tmp;
        pre = tmp;
    }
    return list.get(0);
}

}

2.这个方法不需要创建数组
public class Q_26 {

/**
 * 参照：https://blog.nowcoder.net/n/7ada22418aba4e01be27ef38d557a41c?f=comment
 * 思路：设立一个从尾部遍历到头部的pre节点，在每次递归的时候,把当前节点和pre节点的顺序设置好，然后把pre节点向前移动一个
 */
TreeNode pre = null;
List<TreeNode> list = new ArrayList<>();

public TreeNode Convert(TreeNode pRootOfTree) {
    if (pRootOfTree == null) {
        return null;
    }
    Convert(pRootOfTree.right);
    if (pre == null) {
        pre = pRootOfTree;
    } else {
        pre.left = pRootOfTree;
        pRootOfTree.right = pre;
        pre = pRootOfTree;
    }
    Convert(pRootOfTree.left);
    return pre;
}

}