题目描述：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

解法：

1.非递归

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

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

    }

}
*/
import java.util.Stack;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        //非递归
        if(pRootOfTree==null) return null;
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = pRootOfTree;
        TreeNode pre = null;
        //标记是否为第一次
        boolean flag = true;
        //中序遍历
        while(!stack.isEmpty() || cur!=null){
            while(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if(flag){
                //将中序遍历的第一个节点设为pRootOfTree
                pRootOfTree = cur;
                pre = pRootOfTree;
                flag = false;
            }
            else{
                pre.right = cur;
                cur.left = pre;
                pre = cur;
            }
            cur = cur.right;
        }
        return pRootOfTree;
    }
}