二叉搜索树与双向链表【Java版】

方法一：中序递归
1) 常规版，需要保存头结点

public class Solution {
    TreeNode pre = null;//像这种相邻关系的，设置pre指针
    TreeNode head = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree != null){
            Convert(pRootOfTree.left);
            //由于是中序遍历，所以自动走出有序的顺序
            if(pre == null)head = pRootOfTree;//第一次保存head
            else{//后面n-1次情况
                pre.right = pRootOfTree;
                pRootOfTree.left = pre;
            }
            pre = pRootOfTree;//pre这个全局变量，随着中序的pRootOfTree前进一个节点
            Convert(pRootOfTree.right);
        }
        return head;//只有最外层的return是用上的
    }
}
//时间O(N) 空间O(1)
//如果考虑系统栈的话，空间复杂度就是O(logN)
//【递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度】

2) 升级版：先右后左

public class Solution {
    TreeNode pre =null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree !=null){
            Convert(pRootOfTree.right);//先右后左
            if(pre != null){
                pRootOfTree.right = pre;//这里的left和right是和上面相反的
                pre.left = pRootOfTree;
            }
            pre = pRootOfTree;
            Convert(pRootOfTree.left);
        }
        return pre;
    }
}

方法二：非递归（用栈）

import java.util.Stack;
public class Solution {//二叉树本来就有left、right两个指针位置，初始状态有的为空有的为null
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null)return null;
        Stack<TreeNode> stack = new Stack<TreeNode>();//中序【非递归】，使用【辅助栈】
        TreeNode head = null;
        TreeNode p = pRootOfTree;//指向当前节点
        TreeNode pre = null;//双指针，p前面一个指针
        //用栈模拟中序递归，内部结构也大体一致（都是三步走：向左、处理、向右）
        while(!stack.isEmpty() || p!=null){//【两个不全为空】  //STL判空用.isEmpty()而不用!=null
            //-----------------------------------------------------向左0~n次
            while(p!=null){
                stack.push(p);
                p=p.left;
            }
            //-----------------------------------------------------中序的处理
            p=stack.pop();
            if(pre == null)head=p;
            else{
                pre.right = p;
                p.left = pre;
            }
            pre=p;
            //------------------------------------------------------向右1次
            p=p.right;
        }
        return head;
    }
}

方法三：数组存中序，然后转换（比较low的方法）

import java.util.ArrayList;
public class Solution {
    ArrayList<TreeNode> sortList = new ArrayList<TreeNode>();
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null)return null;
        sort(pRootOfTree);
        set();
        return sortList.get(0);
    }
    public void sort(TreeNode p){
        if(p.left != null)sort(p.left);
        sortList.add(p);//坐实了：add只会存引用，而不是新建
        if(p.right != null)sort(p.right);
    }
    public void set(){
        for(int i=1; i<=sortList.size()-1; ++i){
            sortList.get(i-1).right = sortList.get(i);
            sortList.get(i).left = sortList.get(i-1);
        }
    }
}
//时间O(N) 空间O(N)