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

大致思路就是利用二叉搜索树的中序非递归遍历，利用栈进行遍历二叉树，然后将遍历的结果存放到数组/list当中，之后我们只需要遍历数组/list，数组/list的下一位就是right，前一位就是left

/**
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 {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return pRootOfTree;
        }
      //一下是二叉树的中序非递归遍历
      //定义stack用于进行二叉树的非递归遍历
        Stack<TreeNode> stack = new Stack();
      //定义list存放有序的遍历的结果集
        ArrayList<TreeNode> list = new ArrayList();
      //定义cur保存当前元素
        TreeNode cur = pRootOfTree;
      //当前结点不为空或者栈不为空时进行中序遍历
        while(cur!=null || !stack.isEmpty()){
          //如果当前结点不为空就一直将cur=cur.left，遍历整个二叉树，直到cur为空，
          //说明遍历左子树结束
            while(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
          //在stack不为空时，将当前的栈顶出栈，此时cur=栈顶元素，然后将cur放入到list中，最后将当前结点右移，开始遍历右子树
            if(!stack.isEmpty()){
                cur = stack.pop();
                list.add(cur);
                cur = cur.right;
            }
        }
        
        //中序遍历结束后，list存放的实际上就是有序的结果集，然后我们只需要将
      //list中的当前元素的right指针指向下一位结点，下一位的left指针指向list的前一		//位元素
        for (int i=0;i<list.size()-1;i++){
            list.get(i).right=list.get(i+1);
            list.get(i+1).left=list.get(i);
        }
        
        //最后只需要返回list的首元素即可
        return list.get(0);
    }
}