题目描述：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
解法：
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;
}
}
