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

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 Convert(TreeNode pRootOfTree) {//栈+队列
        Stack<TreeNode> t=new Stack<>();
        Queue<TreeNode> q=new LinkedList<>();
        TreeNode root=pRootOfTree;
        TreeNode temp;
        t.add(pRootOfTree);

        if(pRootOfTree==null)
            return pRootOfTree;
        while(!t.isEmpty()){//先序遍历存入队列

            if(pRootOfTree.left!=null){
                temp=pRootOfTree;
                pRootOfTree=pRootOfTree.left;
                temp.left=null;
                t.push(temp);
              }else{
            
                q.add(pRootOfTree);
                if(pRootOfTree.right!=null){
                    t.push(pRootOfTree.right);
                }
                pRootOfTree=t.pop();
                 
            }
        }
        
        pRootOfTree=q.poll();
        root=pRootOfTree;
        while(!q.isEmpty()){//挨个连串
            temp=q.poll();
            pRootOfTree.right=temp;
            temp.left=pRootOfTree;
            pRootOfTree=temp;
        }

        return root;
    }
}