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

##二叉树搜素树转换成排序的双向的链表其实有好几种方式，但是离不开核心思想，中序遍历。把中序遍历搞明白了就懂了二叉树转换成有序链表。中序遍历有两种方式，一种递归，一种非递归。根据这两种提供几种思路，第一种，通过中序遍历把二叉排序树放入链表，然后在处理成双向链表，第二种非递归的中序，只需要一个保存上一个处理的节点就好了以及一个节点保存根节点，第三种根据非递归的也可以转换成递归的，第四种通过一个反中序，左根右，变成右根左的遍历，这样只需要保存上一个处理的节点就好了。

public class Solution {
    //当前处理过的节点，最后一次就变成头节点了
    TreeNode pre = null;
    public TreeNode Convert(TreeNode root) {
        if (root == null) return null;
        dfs(root);
        //头节点没有头节点
        pre.left = null;
        return pre;
    }
    //这个方法的含义：右根左的遍历方式，构建成双向链表，并把pre置成表头
    public void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.right);
        //上一个节点是最后一个节点不处理，如果不是，把当前节点指向右边的头节点。
        if (pre != null) {
            root.right = pre;
            pre.left = root;
        }
        //每次完成，都要把上一个处理节点变成自己
        pre = root;
        dfs(root.left);
    }
}