剑指offer-26-二叉搜索树转双向链表

思路

二叉搜索树的特点是左<根<右

• 中序遍历结点，用一个数组或者队列存储中序遍历的顺序
• 线索二叉树，比当前结点小的结点中的最大结点是当前结点的前驱结点，相应的另外一个就是后继结点，所以这题就是找到每一个结点的前驱和后继节点，其实就是线索二叉树了

代码

中序遍历

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

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

    }

}
*/
import java.util.*;
public class Solution {
    ArrayList<TreeNode> arr=new ArrayList<>();
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){return pRootOfTree;}
        mid(pRootOfTree);
        TreeNode head=arr.get(0);
        for(int i=0;i<arr.size()-1;i++){
            arr.get(i+1).left=arr.get(i);
            arr.get(i).right=arr.get(i+1);

        }
        arr.get(0).left=null;
        arr.get(arr.size()-1).right=null;
        return head;
    }

    public void mid(TreeNode root){
        if(root==null){
            return;
        }
        mid(root.left);
        arr.add(root);
        mid(root.right);
    }

}