JZ26 二叉搜索树与双向链表

思路：利用ArrayList<treenode>存储TreeNode的中序遍历各个节点，并将节点的左右指针进行指向变化
时间：2021年8月9号</treenode>

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null)
            return null;
        ArrayList<TreeNode> list = new ArrayList<>(); //list存储中序遍历的各个节点

        Convert(list, pRootOfTree);
        TreeNode root = Convert(list);

        return root;
    }
    //中序遍历,并通过list来存储中序遍历的各个节点
    public void Convert(ArrayList<TreeNode> list, TreeNode pRootOfTree) {
        if (pRootOfTree.left != null)
            Convert(list, pRootOfTree.left);
        list.add(pRootOfTree);

        if (pRootOfTree.right != null)
            Convert(list, pRootOfTree.right);
    }

    //修改list中各个节点指针的指向
    public TreeNode Convert(ArrayList<TreeNode> list) {
        int size = list.size();

        if (size == 1){
            list.get(0).left = null;
            list.get(0).right = null;

            return list.get(0);
        }

        if (size == 2) {
            list.get(0).left = null;
            list.get(0).right = list.get(1);
            list.get(1).left = list.get(0);
            list.get(1).right = null;

            return list.get(0);
        }

//         list.get(0).left = null;
//         list.get(0).right = list.get(1); //如果二叉树只有一个节点就会错误

        for (int i = 0; i < size; i++) {
            if (i == 0) {
                list.get(0).left = null;
                list.get(0).right = list.get(1);
            } else if (i == size - 1) {
                list.get(i).left = list.get(i - 1);
                list.get(i).right = null;
            } else {
                list.get(i).right = list.get(i+1);
                list.get(i).left = list.get(i-1);
            }

        }

        return list.get(0);
    }