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

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) {
        if(pRootOfTree==null) return null;
        TreeNode virHead = new TreeNode(-1);
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = virHead ;
        TreeNode cur = pRootOfTree;
        // stack.push(pRootOfTree);
        //中序遍历改变一下就ok
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur =cur.left;
            }
            cur = stack.pop();
             //只修改这部分
            cur.left = pre;
            pre.right = cur;
            pre =cur;

            cur = cur.right;

        }
        //断开虚拟头结点，不然从右往左扫通不过
        TreeNode res = virHead.right;
        virHead.right =null;
        res.left =null;
        return res;
    }
}