二叉搜索树与双向链表

public class Solution {
    TreeNode pRoot=new TreeNode(0) ,p1=pRoot;

    public TreeNode Convert(TreeNode pRootOfTree) {
        dfs(pRootOfTree);
        if(pRoot.right!=null){
            pRoot.right.left=null;
        }
        return pRoot.right;
    }

    public void dfs(TreeNode root){
        if(root==null){
            return;
        }
        dfs(root.left);
        p1.right=root;
        root.left=p1;
        p1=root;
        dfs(root.right);
    }

public class Solution {
    TreeNode const_head = new TreeNode(999);
    TreeNode pre = const_head;

    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        tra(pRootOfTree);
        pre = const_head.right;
        pre.left = null;
        return pre;
    }
    public void tra(TreeNode node){
        if(node.left != null){
            tra(node.left);
        }
        pre.right = node;
        node.left = pre;
        pre = node;
        
        if(node.right != null){
            tra(node.right);
        } 
    }
}

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    // 封装结构 - 该子树的最大结点和最小结点
    // 这里不涉及到新建TreeNode结点，只用作记录已存在的TreeNode结点
    public class Info {
        // 该子树的最大结点
        TreeNode max;
        // 该子树的最小结点
        TreeNode min;

        public Info(TreeNode max, TreeNode min) {
            this.max = max;
            this.min = min;
        }
    }

    // 主方法
    public TreeNode Convert(TreeNode pRootOfTree) {
        // 根据左程云老师讲的【二叉树递归套路】，先弄明白三件事
        // 1.我要干什么：
        //        令root.left   <->   【左子树】的【最大结点】
        //        令root.right  <->   【右子树】的【最小结点】

        // 2.我需要什么信息：
        //      综上所述，我需要左右子树的【最小结点】和【最大结点】，可以把它们【封装】进一个数据结构中，方便递归函数的return

        // 3.我如何利用两个子树的信息加工出来我的信息：
        //      根据二叉搜索树的性质：
        //      root的【最大结点】 = 【右子树】的【最大结点】 或者 【root】
        //      root的【最小结点】 = 【左子树】的【最小结点】 或者 【root】


        // 调用递归函数生成双向链表，并返回这个双向链表的最左头结点
        Info resultInfo = process(pRootOfTree);

        return resultInfo.min;
    }

    // 递归序遍历二叉树函数 - 返回以root为根结点的子树的最大结点和最小结点
    public Info process(TreeNode root) {
        // 递归出口
        if (root == null) {
            // 当结点为空时，说明这一子树的max和min都是null
            return new Info(null, null);
        }

        // 记录左子树和右子树的最小结点和最大结点
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);

        // 拿到左右子树的Info后做两件事:
        // 1.令root.left <-> 【左子树】的【最大结点】；root.right <-> 【右子树】的【最小结点】
        root.left = leftInfo.max;
        if (leftInfo.max != null) {
            leftInfo.max.right = root;
        }
        root.right = rightInfo.min;
        if (rightInfo.min != null) {
            rightInfo.min.left = root;
        }
        // 2.生成自己的Info信息并返回
        TreeNode myMax = (rightInfo.max != null) ? rightInfo.max : root;
        TreeNode myMin = (leftInfo.min != null) ? leftInfo.min : root;

        return new Info(myMax, myMin);
    }
}

public class Solution {

    private TreeNode pre = null;

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (null == pRootOfTree) {
            return null;
        }
        inorder(pRootOfTree);
        TreeNode head = pRootOfTree;
        while (head.left != null) {
            head = head.left;
        }
        return head;
    }

    private void  inorder(TreeNode root) {
        if (null == root) {
            return ;
        }
        inorder(root.left);
        if (pre != null) {
            pre.right = root;
            root.left = pre;
        }
        pre = root;
        inorder(root.right);
    }

}

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    TreeNode res = null;
    TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        midOrder(pRootOfTree);
        return res;
    }
    public void midOrder(TreeNode root) {
        if(root != null) {
            midOrder(root.left);
            if(res == null) {
                res = root;
                pre = root;
            } else {
                pre.right = root;
                root.left = pre;
                pre = root;
            }
            midOrder(root.right);
        }
    }
}

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;
        InOrder(pRootOfTree);
        TreeNode p = pRootOfTree;
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }
    public void InOrder(TreeNode Root) {
        if (Root == null) {
            return;
        }
        InOrder(Root.left);
        Root.left = pre;
        if (pre != null) {
            pre.right = Root;
        }
        pre = Root;
        InOrder(Root.right);
    }
}

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {

    public TreeNode prev = null;

    public void convertChild(TreeNode pCur) {
        if(pCur == null) {
            return;
        }
        convertChild(pCur.left);

        pCur.left = prev;
        if(prev != null) {
            prev.right = pCur;
        }
        prev = pCur;
        convertChild(pCur.right);

    }

    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }
        convertChild(pRootOfTree);
        TreeNode head = pRootOfTree;

        while(head.left != null) {
            head = head.left;
        }
        return head;
    }
}

public class Solution {
    TreeNode head=null;//赋初值为null
    TreeNode pre=null;
    //双向链表必然要定义head、pre
    public TreeNode Convert(TreeNode pRootOfTree) {
        build(pRootOfTree);
        return head;
    }
    public void build(TreeNode root){
        //必然是中序遍历
        if(root==null) return ;
        build(root.left);
        if(pre==null){
            pre=root;
            head=root;
        }else{
            pre.right=root;//这里head、pre定义为TreeNode  所以这里是pre.right  head.left
            root.left=pre;//root来回倒
            pre=root;
        }
        build(root.right);

    }

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }
}
*/

public class Solution {
    public TreeNode pre=null;
    public TreeNode head=null;
    public TreeNode Convert(TreeNode root) {
        //如果根节点为空则为空
        if(root==null){
            return null;
        }
        //用来保存创建的双向链表
        ArrayList<TreeNode> tree=new ArrayList<>();
        //中序遍历
        mid(root,tree);
        //清空tree节点每个左右分支
        for(int i=0;i<tree.size();i++){
            TreeNode tmp=tree.get(i);
            tmp.left=null;
            tmp.right=null;
        }
        //开始构建从左到右单向链表
        for(int i=0;i<tree.size()-1;i++){
            TreeNode tmp=tree.get(i);
            tmp.right=tree.get(i+1);
        }
        //开始构建从右到左的单向链表
        for(int i=tree.size()-1;i>0;i--){
            TreeNode tmp=tree.get(i);
            tmp.left=tree.get(i-1);
        }
        //返回第一个tree节点，就是双向链表的头节点
        return tree.get(0);
    }
    public void mid(TreeNode root,ArrayList<TreeNode> tree){
        if(root==null){
            return;
        }
        mid(root.left,tree);
        tree.add(root);
        mid(root.right,tree);
    }
}